누적합(Prefix Sum)

공부하기/Algorithm

누적합(Prefix Sum)

다섯자두 2024. 1. 23. 09:20

누적합 알고리즘의 정의

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

수열 \(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번째 원소까지 계속해서 더해온 값을 의미한다.
모든 구간에 대해 단순 계산하는 것이 아니라, 이전 인덱스까지의 누적합을 이용하여 현재 인덱스의 누적합을 계산하는 것이 효과적인 누적합 알고리즘이다.