누적합(Prefix Sum)

누적합 알고리즘의 정의

누적합 알고리즘은 말 그대로 어떠한 구간의 누적된 합을 구하는 알고리즘이다.

수열 \(A_n\)에 대하여 특정 인덱스 a에서 b까지의 구간 합을 구하는 알고리즘이라고도 볼 수 있다.

예시

[ 1,2,3,4,5 ] 로 이루어진 크기가 5인 배열 arr가 있다. 
이 때 arr[1] 부터 arr[3]의 구간 합을 구해보자.

(방법 1)
가장 쉬운 방법으로, 2부터 4까지 인덱스를 하나씩 증가시키며 배열을 방문하여 요소들을 더한다.
1
1+2
1+2+3 = 6

만일 배열의 처음부터 해당 인덱스까지의 합을 나타내는 배열 [ 1,2,6,10,15 ]을 구하려고 하면 어떨까?
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5
위를 보면 알 수 있듯이, 0을 제외한 모든 인덱스에서 자신 이전 인덱스에서 수행된 연산을 반복하게 됨을 알 수 있다.
이는 배열의 원소 수가 n개 일 때 \(O(n^2)\)의 시간복잡도를 갖는다.

(방법 2)
이전 인덱스에서 수행된 연산 결과, 즉 이전 인덱스까지의 누적합에 현재 인덱스의 값을 더하면 중복된 연산을 줄일 수 있으며, 이것이 효과적인 누적합 알고리즘이다.
1
1+2 (3)
3+3 (6)
6+4 (10)
10+5 (15)
이는 배열의 원소 수가 n개 일 때 \(O(n)\)의 시간복잡도를 갖는다.

 

정리하자면 다음과 같다.

• 누적합이란 수열 \(A_n\)에서 특정 인덱스까지의 구간 합을 의미한다.
• 첫번째 원소부터 i번째 원소까지 계속해서 더해온 값을 의미한다.
• 모든 구간에 대해 단순 계산하는 것이 아니라, 이전 인덱스까지의 누적합을 이용하여 현재 인덱스의 누적합을 계산하는 것이 효과적인 누적합 알고리즘이다.

배열 [i]~[j] 인덱스 범위의 누적합을 구해야할 때
1. 해당 배열에 대한 누적합 배열을 구한다.
2. 배열 [i~j] 범위의 누적합 = 누적합[j] - 누적합[i-1] 으로 계산한다.

 

예시

[ 1,2,3,4,5 ] 로 이루어진 크기가 5인 배열 arr가 주어질 경우,

누적합 배열 preSum을 구해놓는다.

preSum = [ 1,3,6,10,15 ]

 

arr의 2번째 요소부터 4번째 요소까지의 구간합은 = preSum[3]-preSum[0] = 9

arr의 인덱스 1부터 인덱스 4까지의 구간합은 = preSum[4]-preSum[0] = 14

 

 

누적합 문제

- 백준

https://www.acmicpc.net/step/48

- 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/92344

https://school.programmers.co.kr/learn/courses/30/lessons/72414

---