동호의 블로그

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

누적합 알고리즘은 영어로 Prefix Sum 알고리즘이라고 많이 부른다.

(전저리 후에) 1차원 배열 또는 2차원 배열에서 연속된 구간의 합을 만에 구하는 알고리즘이다.

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

배열의 길이를 이라고 할 때, 의 전처리를 수행하면 된다.

DP 테이블 설계

: ~번째 원소까지의 합

관계식

부터 까지 원소의 합을 구하는 방법

예제코드


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차원 배열의 세로 길이를 , 가로 길이를 이라고 할 때, 의 전처리를 수행하면 된다.

DP 테이블 설계

: 부터 까지의 2차원 합

관계식

(sy, sx)부터 (ey, ex)까지의 2차원 합 구하는 방법

예제코드


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차원 배열의 누적합

연속된 합의 구간을 여러 번 구해야 할 때 쓰면 효율적이다.

2차원 배열의 누적합

(직사각형 모양의) 2차원 합을 여러 번 구해야 할 때 쓰면 효율적이다.

관련 문제