누적합 알고리즘

1차 카테고리
알고리즘
2차 카테고리
dynamic programming
생성 일시
2025/01/11 15:55
최종 편집 일시
2025/01/23 05:51
발행여부
published

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

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

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

•
배열의 길이를 NN이라고 할 때, O(N)O(N)의 전처리를 수행하면 된다.
•
DP Table 설계
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]
아래와 같은 문제에서 열을 끊어주는 경우에 0으로 비교하는 로직 생각이 어려웠다.
www.acmicpc.net
https://www.acmicpc.net/problem/1912

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

•
2차원 배열의 세로 길이를 NN, 가로 길이를 MM이라고 할 때, O(NM)O(NM)의 전처리를 수행하면 된다.
•
DP Table 설계
psum[n][m]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])

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

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