Skip to main content
동호의 블로그

다이나믹 프로그래밍(DP) 알고리즘 : 누적합 알고리즘

•1 min•195 words

1. 누적합 알고리즘이란?

  • 누적합 알고리즘은 영어로 Prefix Sum 알고리즘이라고 많이 부른다.
  • (전저리 후에) 1차원 배열 또는 2차원 배열에서 연속된 구간의 합을 O(1)O(1)만에 구하는 알고리즘이다.

2. 1차원 배열에서 누적합 알고리즘

  • 배열의 길이를 NN이라고 할 때, O(N)O(N)의 전처리를 수행하면 된다.
  • DP 테이블 설계
$psum[n]$: $1$~$n$번째 원소까지의 합

4a69eba7-b7c4-4e85-88ed-fee355aa49ff.png

  • 관계식
$psum[n] = psum[n-1] + arr[n]$

89e2911a-5e34-48c5-9542-9f90f39bbaaa.png

  • aa부터 bb까지 원소의 합을 구하는 방법
$psum[b] - psum[a-1]$

image.png

예제코드 
def get_sum(a, b): # a부터 b까지의 원소의 합 반환
	global psum
	return psum[b] - psum[a - 1]

N = 9

arr = [0, 1, 3, 10, -2, 3, -4, 10, 3, 8] # 1인덱스
psum = [0] * (N + 1)

# psum 갱신
for n in range(1, N + 1):
	psum[n] = psum[n - 1] + arr[n]

# 2부터 8까지의 합
print(get_sum(2, 8))

3. 2차원 배열에서 누적합 알고리즘

  • 2차원 배열의 세로 길이를 NN, 가로 길이를 MM이라고 할 때, O(NM)O(NM)의 전처리를 수행하면 된다.
  • DP 테이블 설계
$psum[n][m]$: $(1, 1)$부터 $(n, m)$까지의 2차원 합

image.png

  • 관계식
$psum[n][m] = (psum[n][m-1] + psum[n-1][m] - psum[n-1][m-1]) + arr[n][m]$

image.png

  • (sy, sx)부터 (ey, ex)까지의 2차원 합 구하는 방법
$psum[ey][ex] - (psum[ey][sx-1] + psum[sy-1][ex] - psum[sy-1][sx-1])$

image.png

예제코드 
def get_sum(sy, sx, ey, ex): # (sy, sx)부터 (ey, ex)까지의 2차원 합 반환
	global psum
	return psum[ey][ex] - (psum[ey][sx - 1] + psum[sy - 1][ex] - psum[sy - 1][sx - 1])

N = 4
M = 5

arr = [
	[0, 0, 0, 0, 0, 0],
	[0, 10, 10, 3, 8, 4],
	[0, 9, 8, 4, 1, 10],
	[0, 7, 6, 5, 6, 5],
	[0, 2, 6, 6, 4, 10]
]
psum = [[0 for _ in range(M + 1)] for _ in range(N + 1)]

# psum 갱신
for n in range(1, N + 1):
	for m in range(1, M + 1):
		psum[n][m] = (psum[n - 1][m] + psum[n][m - 1] - psum[n - 1][m - 1]) + arr[n][m]

# (3, 3)부터 (4, 5)까지의 2차원 합
print(get_sum(3, 3, 4, 5))

4. 누적합 알고리즘은 언제 쓸까?

1차원 배열의 누적합
  • 연속된 합의 구간을 여러 번 구해야 할 때 쓰면 효율적이다.
    • O(N3)O(N^3) → O(N2)O(N^2)
2차원 배열의 누적합
  • (직사각형 모양의) 2차원 합을 여러 번 구해야 할 때 쓰면 효율적이다.
    • O((NM)3)→O((NM)2)O((NM)^3) → O((NM)^2)