[DP] 누적합 알고리즘

누적합 알고리즘은 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있는 알고리즘이다.

N개의 원소로 이루어진 배열이 주어졌을 때, 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 부분 합을 이용하면 모든  부분합을 O(1)에 바로 구할 수 있다.

 

KeyPoint

• sum은 배열의 +1이다.

 

1차원 배열

- 직관적으로 매우 쉽게 이해가 가능하다. arr 을 순차 탐색하면서 sum배열을 만들어주면 된다.

sum[i]에는 arr[0] + arr[i] + ...+ㅁㄱㄱ[i-1]의 정보가 담겨 있다.

활용법

arr의 i항부터 j항까지의 합을 s(i,j)라고 하자.

이때, s(i,j) = sum[j+1] - sum[i]이다.

2차원 배열

2차원 배열도 같은 방식이다. arr을 순차 탐색하면서 sum 배열을 만들어 주면 된다.

이때 sum[i][j]에는 arr[0][0]부터 arr[i-1][j-1]까지의 합이 담겨 있다고 생각하면 된다.

그림으로 보면 바로 이해 가능

이때 그럼 sum배열은 어떻게 만드는지는 아래와 같이 반복문을 돌려주면 된다.

이때 기억해놓으면 좋은 식은 아래와 같다.

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

arr = [[1, 2, 3, 4],
	[2, 3, 4, 5],
    	[3, 4, 5, 6],
    	[4, 5, 6, 7]]
m = 4
n = 3

sum_arr = [[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):
		sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1]- sum_arr[i-1][j-1]

2차원 구간 합 활용법

이제 이 sum_arr 을 활용하면 2차우너 배열에서도 상수 시간에 구간합을 구할 수 있다.

arr의 (x1,y1)부터 (x2,y2)까지 합을 S라 할때, 아래와 같이 구할 수 있다.

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