누적합(Prefix Sum)의 원리와 구간 합 계산 - soo:bak
작성일 :
누적합이란?
누적합(Prefix Sum) 은 배열의 특정 구간 합을 빠르게 계산하기 위한 기법입니다.
다음과 같은 배열이 있고, 여러 구간의 합을 반복적으로 구해야 한다고 가정해봅시다:
1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
구간 [2, 5]의 합을 구하려면 arr[2] + arr[3] + arr[4] + arr[5]를 계산해야 합니다.
단순히 반복문으로 구현하면 각 쿼리마다 \(O(N)\)의 시간이 소요되며,
쿼리가 M개라면 전체 시간 복잡도는 \(O(N \times M)\)이 됩니다.
예를 들어, 배열의 크기가 100,000이고 쿼리가 100,000개라면,
약 100억 번의 연산이 필요하게 됩니다.
누적합은 배열의 처음부터 각 위치까지의 합을 미리 계산해 두어,
임의의 구간 합을 단 한 번의 뺄셈으로 구할 수 있게 합니다.
이를 통해 각 쿼리를 \(O(1)\) 시간에 처리할 수 있게 됩니다.
누적합의 원리
누적합 배열 sum은 배열의 처음부터 각 위치까지의 합을 저장합니다:
즉, sum[i]는 배열의 첫 번째 원소부터 i번째 원소까지의 합입니다.
누적합 배열 구성
위 예시 배열 [3, 1, 4, 1, 5, 9, 2, 6]에 대한 누적합 배열을 구성하면:
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| arr | 3 | 1 | 4 | 1 | 5 | 9 | 2 | 6 |
| sum | 3 | 4 | 8 | 9 | 14 | 23 | 25 | 31 |
각 위치의 누적합은 다음과 같이 계산됩니다:
sum[0] = 3sum[1] = 3 + 1 = 4sum[2] = 3 + 1 + 4 = 8sum[3] = 3 + 1 + 4 + 1 = 9- …
구간 합 계산
누적합 배열을 이용하면 임의의 구간 [i, j]의 합을 다음과 같이 계산할 수 있습니다:
이는 다음과 같은 원리입니다:
sum[j]는 처음부터j까지의 합sum[i-1]은 처음부터i-1까지의 합- 따라서
sum[j] - sum[i-1]은i부터j까지의 합
예를 들어, 구간 [2, 5]의 합을 구해봅시다:
이는 arr[2] + arr[3] + arr[4] + arr[5] = 4 + 1 + 5 + 9 = 19와 동일합니다.
반복문으로는 4번의 덧셈이 필요하지만, 누적합을 사용하면 단 1번의 뺄셈으로 같은 결과를 얻을 수 있습니다.
구현
1차원 누적합
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; // n: 배열 크기, m: 쿼리 개수
cin >> n >> m;
vector<int> arr(n);
vector<int> sum(n + 1, 0); // sum[0] = 0으로 초기화
// 누적합 배열 구성
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum[i + 1] = sum[i] + arr[i]; // 이전 누적합 + 현재 값
}
// 구간 합 쿼리 처리
for (int i = 0; i < m; i++) {
int start, end;
cin >> start >> end;
// sum[end] - sum[start-1]로 구간 합 계산
cout << sum[end] - sum[start - 1] << "\n";
}
return 0;
}
시간 복잡도: 전처리 \(O(N)\), 각 쿼리 \(O(1)\)
2차원 누적합
2차원 배열에서도 누적합을 적용하여 직사각형 영역의 합을 빠르게 계산할 수 있습니다.
2차원 누적합 배열 sum[i][j]는 (0, 0)부터 (i, j)까지의 직사각형 영역의 합을 의미합니다.
2차원 누적합 구성
2차원 누적합은 다음과 같이 계산됩니다:
\[\text{sum}[i][j] = \text{arr}[i][j] + \text{sum}[i-1][j] + \text{sum}[i][j-1] - \text{sum}[i-1][j-1]\]
여기서 sum[i-1][j-1]을 빼는 이유는, sum[i-1][j]와 sum[i][j-1]에 모두 포함되어 중복되기 때문입니다.
2차원 구간 합 계산
(x1, y1)부터 (x2, y2)까지의 직사각형 영역의 합은 다음과 같이 계산됩니다:
마찬가지로 sum[x1-1][y1-1]을 더하는 이유는, 빼는 두 영역에 모두 포함되어 중복으로 빠지기 때문입니다.
2차원 누적합 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; // n: 행, m: 열
cin >> n >> m;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
vector<vector<int>> sum(n + 1, vector<int>(m + 1, 0));
// 2차원 누적합 배열 구성
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
// 현재 칸 + 위쪽 누적합 + 왼쪽 누적합 - 대각선 누적합
sum[i][j] = arr[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
int k; // 쿼리 개수
cin >> k;
while (k--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// 전체 영역 - 위쪽 영역 - 왼쪽 영역 + 대각선 영역
int result = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
cout << result << "\n";
}
return 0;
}
시간 복잡도: 전처리 \(O(N \times M)\), 각 쿼리 \(O(1)\)
시간 복잡도
누적합의 시간 복잡도는 다음과 같습니다:
누적합 배열 구성
배열의 모든 원소를 한 번씩 순회하므로:
\[O(N)\]구간 합 쿼리
누적합 배열을 활용하면 각 쿼리를 \(O(1)\) 시간에 처리할 수 있습니다.
따라서 M개의 쿼리에 대한 전체 시간 복잡도는:
단순 반복문으로 구현한 \(O(N \times M)\)에 비해 훨씬 효율적입니다.
쿼리가 많을수록 누적합의 효율성이 극대화됩니다.
누적합의 활용
누적합은 다양한 형태로 확장하여 활용할 수 있습니다.
1. 구간 합 쿼리
가장 기본적인 활용으로, 배열의 특정 구간 합을 반복적으로 구해야 하는 문제에 사용됩니다.
2. 구간 평균 계산
구간의 합을 구한 뒤 구간의 길이로 나누면 평균을 계산할 수 있습니다.
\[\text{평균} = \frac{\text{sum}[j] - \text{sum}[i-1]}{j - i + 1}\]3. 차분 배열 (Difference Array)
누적합의 역연산으로, 구간에 일정한 값을 더하는 쿼리를 효율적으로 처리할 수 있습니다.
차분 배열 diff[i] = arr[i] - arr[i-1]를 구성하면,
구간 [L, R]에 x를 더하는 연산을 diff[L] += x, diff[R+1] -= x로 \(O(1)\)에 처리할 수 있습니다.
모든 쿼리를 처리한 후 차분 배열의 누적합을 구하면 최종 배열을 얻을 수 있습니다.
4. 2차원 구간 합
행렬의 부분 직사각형 영역의 합을 빠르게 계산할 수 있습니다.
이미지 처리, 게임 맵 분석 등에서 자주 사용됩니다.
마무리
누적합은 배열의 구간 합을 효율적으로 계산하기 위한 기법입니다.
전처리로 \(O(N)\) 시간에 누적합 배열을 구성하면,
이후 각 구간 합 쿼리를 \(O(1)\) 시간에 처리할 수 있어,
쿼리가 많은 문제에서 단순 반복문에 비해 훨씬 효율적입니다.
1차원 배열뿐만 아니라 2차원 배열로 확장할 수 있으며,
차분 배열과 결합하여 구간 업데이트 쿼리를 효율적으로 처리할 수도 있습니다.
관련 문제: