[Algorithm] 누적 합(Prefix Sum, Cumulative Sum)

누적 합(Prefix Sum, Cumulative Sum)

- 말 그대로 나열된 수의 누적된 합을 말한다.

- 수열 An에 대해서, 구간 [1,1]의 합, 구간 [1, 2]의 합, 구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다.

An	1	2	3	4	5
Prefix Sum	1	3	6	10	15

 

누적 합의 사용

- 목적에 따라 다양한 문제에 활용이 가능하다.

- 대표적으로 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다.

 

단순 반복을 이용한 구간 합 구하기

- 모든 입력마다 구간 합을 일일히 구해주는 경우 구간의 길이가 M이라고 하면 매 구간합을 구할 때마다 O(M)이라는 시간이 걸리게 된다. N개의 구간에 대해 구간의 길이가 M인 구간합을 구하는 경우 O(NM)의 시간이 걸린다.

ex) [1, 200000] 에서 각 자연수를 시작점으로 구간의 길이가 10000인 구간 합을 모두 구하려면 총 20억 번가량의 연산 진행

 

누적 합을 이용하여 구간 합 구하기

- 수열 An에서 구간 [i, j]까지의 구간 합을 구하는 경우를 생각해보면 

그림과 같이 n항까지의 합을 Sn이라고 정의하면, 구간 [i,j]의 구간합은 Sj에서 Si-1을 뺀 값으로 바로 구할 수 있다.

- Sn까지의 구간 합을 모두 구해 놓으면 (O(M)) 구간 합을 구하는 연산 자체는 O(1)의 시간이므로 결론적으로 O(N+M)의 시간복잡도를 갖는다.

 

 

활용법

- sum은 arr의 길이보다 +1 길게 설정한다.

- arr의 i부터 j까지의 합을 S(i, j)라고 하면 S(i, j) = sum[j+1] - sum[i]이다.

 

2차원 배열

- 2차원 배열도 같은 방식으로 arr을 순차 탐색하면서 sum 배열을 만들어준다.

- arr가 (nxm) 이라면 sum은 첫번째 행과 열에 0을 추가하여 (n+1 x m+1) 형태로 만들어준다.

- sum[i][j] = arr[0][0] 부터 arr[i-1][j-1]까지의 합

구현

prefix_sum = [[0 for _ in range(m+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        prefix_sum[i][j] = arr[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]

2차원 구간 합 활용법

arr의 (x1, y1) 부터 (x2, y2)까지 합을 S라 할 때, 

S = sum[x2+1][y2+1] - sum[x2][y2+1] - sum[x2][y2+1] - sum[x2+1][y2] + sum[x1][y1]

- 좌표가 인덱스 번호가 아니라면 각 좌표 값에 -1

위 사진으로 봤을 때 10은 arr의 (0,0) ~ (3,0)까지의 합이고, 6은 (0,0) ~ (0,2)까지의 합이다.

(1,1) ~ (3,2)까지 구하기 위해서 (0,0) ~ (3,2) 까지의 합인 42에서 10과 6을 빼주고 중복되어 빠진 1 (0,0)을 빼준다.

 

+ 누적 합 참고 문제

https://minjoo-happy-blog.tistory.com/97?category=1110208 

[프로그래머스] 파괴되지 않은 건물

백준 

- 2167 문제 추천

 

 

참고 자료

https://yiyj1030.tistory.com/489