누적합 Prefix Sum

누적합이란

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다.

 

항상 문제를 풀 때는 최대, 최소 범위를 확인하고 생각을 해봅시다.

 

"구간 쿼리" 하면 2가지가 생각나야 합니다.

• 팬윅트리(동적 배열)
• pSum(정적 배열)

예시문제 - 큰돌의 터전

예시 문제 - 큰돌의 터전

 

[핵심]

처음과 끝의 합은 변하지 않습니다.(정적 배열이기 때문입니다.)

매번 더할 필요없이 각 구간에 맞게 뺄셈만 해주면 됩니다.

 

 

 

[코드 1]

이 코드는 위의 핵심을 완전히 파악하지 못하고 작성한 코드입니다.

처음에 문제를 풀 때, 입력 받는 인덱스를 임의로 tempStart/tempEnd에 저장하고

다음에 입력받는 인덱스와 비교했을 때 경우를 나누어서 진행했습니다.

 

예를 들어, '1 4' 입력 후 '1 5'를 입력한다면

'1 4'의 결과값을 vN[0]에 저장하고 vN[5]만 vN[0]에 더하여 result에 대입하였습니다.

 

[코드 2]

코드 2는 "큰돌의 터전의 큰돌님의 코드"를 참고한 것입니다. 

코드를 보고 아직 한참 부족하다는 것을 바로 느꼈습니다..:(

 

위에서 [핵심]에서 언급했듯이 정적인 배열의 특성을 잘 활용한 코드인 것 같습니다.

큰돌님의 코드

 

psum배열의 각 인덱스까지 요소들의 합을 대입하고 있습니다.

그래서 인덱스는 1부터 시작하여 0번도 접근할 수 있도록 합니다.

 

마지막에는 end Index에서 start Index까지의 합을 서로 빼면 답이 나오게 됩니다.

 

이 문제에서 얻어갈 것은

코드를 먼저 작성하는 것이 아니라

문제를 해석하는 시간이 필요하다는 것입니다.

 

이 문제는 크게 어려운 문제가 아니어서 바로 코드를 작성할 수도 있었습니다.

그렇게 되면 문제가 발생하게 됩니다.

왜냐하면 문제의 범위가 100,000까지이기 때문입니다..!!

 

그렇기 때문에 생각하고 해석하는 시간을 갖는 연습이 중요한 것 같습니다.

 

 

 

 

참고: 큰돌의 터전,https://youtu.be/906Kko5nZhE