[알고리즘] 누적합 알고리즘 (Prefix sum algorithm)

누적합 (Prifix sum)

나열된 수의 누적된 합

배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있도록 함

 

구간 합 구하기

N개의 원소로 이루어진 배열에서 구간 합을 구하는 방법

1. 반복문을 통한 구간 합
   • 배열의 i번째 원소부터 j번째 원소까지 순회하며 값을 더함
   • 구간 [i, j]의 합 = arr[i] + arr[i+1] + ... + arr[j]
   • 시간복잡도: O(N)
     • 구간의 길이에 비례하여 시간이 증가하기 때문에 여러 번 구간 합을 구해야 할 때 비효율적
2. 누적합 알고리즘 사용
   • 미리 배열의 누적합 배열을 계산
   • 누적합 배열 S에서 S[k]는 배열의 0번째 원소부터 k번째 원소까지의 합을 의미
   • 구간 [i, j]의 합 = S[j] - S[i - 1]
   • 시간복잡도: O(1)
     • 누적합 배열을 미리 계산하는 데 O(N)
     • 이후 각 구간 합을 O(1)에 구할 수 있어 여러 구간에 대한 합을 효율적으로 계산할 수 있음

 

누적합 알고리즘 (Prefix sum Algorithm)

1차원 배열

주어진 input numbers(arr)를 순차적으로 탐색하면서 prefix sums(S) 배열을 만듦

input numbers (arr)	1	2	3	4	5	6	7	...
prefix sums (S)	1	3	6	10	15	21	28	...

S의 i번째 원소의 값은 arr의 1번째부터 i번째 원소까지의 합

• S[i] = S[i-1] + arr[i]

 

arr의 i번째 원소부터 j번째 원소까지의 합은 S[j] - S[i - 1]

prefix sums (S)

1

3

6

10

15

21

28

prefix sums (S)

1

3

6

10

15

21

28

예를 들어, 4번째 원소부터 6번째 원소까지의 합은 S[6] - S[3]

1~6번째 원소의 합에서 1~3번째 원소의 합을 빼야 4~6번째 원소의 합이 나옴

 

2차원 배열

1차원 배열과 마찬가지로 arr 배열을 순차 탐색하며 sum 배열을 만듦

 

arr

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

sum (S)

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

 

sum[i][j]는 arr[0][0]부터 arr[i][j]까지의 합

 

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

코드상으로 구현하기 편하게 하기 위해 sum 배열의 가로세로를 1씩 늘린다

이때 sum[i][j]는 arr[0][0]부터 arr[i-1][j-1]까지의 합

 

sum 배열 만드는 공식

S[i][j] = arr[i-1][j-1] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]

 

예를 들어, S[3][2]를 구하기 위해선

arr[2][1]

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

+ sum[2][2]

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

+ sum[3][1]

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

- sum[2][1]

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

즉 S[3][2]의 값을 구할 때

S[2][2]와 S[3][1]을 더한 후, 두 배열이 중복되는 부분인 S[2][1]을 제외한 뒤 arr[2][1]의 값을 더하면 됨

---

 

참고

• https://san-tiger.tistory.com/entry/Prefix-sum-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B4%EB%9E%80
• https://velog.io/@alkwen0996/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%88%84%EC%A0%81%ED%95%A9Prefix-Sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9Prefix-Sum-of-Matrix
• https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java