Search

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

생성일
2024/08/11

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

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

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

•
배열의 길이를 NN이라고 할 때, O(N)O(N)의 전처리를 수행하면 된다.
•
DP 테이블 설계
psum[n]psum[n]: 11~nn번째 원소까지의 합
•
관계식
psum[n]=psum[n−1]+arr[n]psum[n] = psum[n-1] + arr[n]
•
aa부터 bb까지 원소의 합을 구하는 방법
psum[b]−psum[a−1]psum[b] - psum[a-1]
예제코드

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

•
2차원 배열의 세로 길이를 NN, 가로 길이를 MM이라고 할 때, O(NM)O(NM)의 전처리를 수행하면 된다.
•
DP 테이블 설계
psum[n][m]: (1, 1)부터 (n, m)까지의 2차원 합
•
관계식
psum[n][m]=(psum[n][m−1]+psum[n−1][m]−psum[n−1][m−1])+arr[n][m]psum[n][m] = (psum[n][m-1] + psum[n-1][m] - psum[n-1][m-1]) + arr[n][m]
•
(sy, sx)부터 (ey, ex)까지의 2차원 합 구하는 방법
psum[ey][ex]−(psum[ey][sx−1]+psum[sy−1][ex]−psum[sy−1][sx−1])psum[ey][ex] - (psum[ey][sx-1] + psum[sy-1][ex] - psum[sy-1][sx-1])
예제코드

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

1차원 배열의 누적합
2차원 배열의 누적합
•
관련 문제