누적합의 필요성
알고리즘 문제를 풀다보면 배열의 부분합을 빠르게 구해야 하는 경우가 있다.
필요할 때 마다 구하게 되면 구할 때 마다 O(N)의 시간 복잡도를 갖는다.
종만북 1번 문제 페스티벌을 한번 보자.
https://algospot.com/judge/problem/read/FESTIVAL
가장 Naive한 알고리즘의 경우, 연속된 구간합을 구해서 그때그때마다 최소인지 모두 확인해 보는 방법인데, 구간합을 구하면 O(N2)의 시간 복잡도를 갖기 때문에 상당히 느리다.
하지만 누적합을 이용하면 연속된 구간합을 O(N)만에 구할 수 있다.
누적합의 개념
대충 아래와 같은 수열이 있다고 해 보자. 총 5개의 원소를 가지고 있다.
인덱스 번호 |
1 |
2 |
3 |
4 |
5 |
ai |
3 |
5 |
7 |
1 |
4 |
Si |
3 |
8 |
15 |
16 |
20 |
위 수열에서 연속된 구간의 합, 예를들어 a2부터 a4까지의 합을 구하려고 한다면, 3개의 원소 값을 참조해야 한다.
이러한 점을 보완하기 위해서 누적합 수열 Si를 도입해보자.
Si는 a1부터 ai까지의 모든 원소의 합을 자신의 값으로 갖는다. 또한 S0=0이다.
i번째 원소부터 j번째 원소의 구간합은 Sj−Si−1으로 구할 수 있다.
누적합 수열의 성질
1. S0=0 2. S1=a1 3. Si=Si−1+ai 4. Sn=a1+a2+...+an−1+an
5. ai+ai+1+...+aj−1+aj=Sj−Si−1
누적합을 활용한 빠른 구간합 계산
위의 누적합 수열의 성질 중 5번째 성질을 이용해서 연속된 임의의 구간의 합을
O(1)의 시간복잡도에 구할 수 있다. 다만 유의해야 할 사항은, 코드로 옮길 때, 누적합의 값이 산술 오버플로(Arithmetic Overflow)가 나타날 수 있으므로 변수 크기를 잘 조절해야 한다.
누적합을 이용해서 페스티벌 문제를 풀어본 코드이다.
페스티벌 문제 풀이 코드
#include <stdio.h>
#include <stdlib.h>
void dump_arr(int* arr, int len) {
for (int i=0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int case_num, total_num, least_len, i, j, k, start, len, sum;
int* arr, *summation;
double min, current;
scanf("%d", &case_num);
for (i=0; i< case_num; i++) {
scanf("%d %d", &total_num, &least_len);
arr = (int*) calloc(sizeof(int), total_num);
summation = (int*) calloc(sizeof(int), total_num + 1);
summation[0] = 0;
for (j=0; j< total_num; j++) {
scanf("%d", &arr[j]);
summation[j+1] = summation[j] + arr[j];
}
min = 9999999999;
int start, end;
for (start = 0; start <= total_num - least_len; start++) {
for (end = start + least_len ; end <= total_num; end++) {
current = (double)(summation[end] - summation[start]) / (end-start);
if (min > current) {
min = current;
}
}
}
printf("%.10f\n", min);
free(arr);
free(summation);
}
}
2차원 누적합
위에서 언급한 누적합의 개념을 2차원으로 확장시킬 수 있다. 2차원 누적합으로 해결할 수 있는 문제의 예시로는 다음 Star sky 문제가 있다.
누적합이 2차원으로 확장되면서 일차원 배열은 2차원 배열로 확장되고, 누적합 수열도 2차원 배열형태로 확장된다.
직사각형 형태의 배열에 포함되는 직사각형 구간의 모든 원소의 합을 빠르게 구할 수 있게 된다.
다음과 같이 2차원 배열 a(i,j)과 2차원 누적합 배열 S(i,j)가 있다고 가정해보자.
가장 왼쪽 위를 a(1,1)라고 할 때 S(i,j)는 a(1,1)와 a(i,j)를 양 대각 끝 꼭지점으로 하는 직사각형 범위 면적 안의 모든 a 원소의 합으로 정의된다.
a(2,2) a(3,3)의 부분합을 구하기 위해서는 S(3,3)에서 시작한다.
S(3,3)값에서 S(1,3)값을 빼고, S(3,1) 값을 빼면 초록색 부분의 합에서 주황색 부분의 합이 빠진 값이 된다
. 왜냐하면 S(1,3)값에 주황색 부분이 포함되어 있고, S(3,1)부분에도 주황색 부분의 값이 포함되어 있으니, 두번 빼진 셈 이다.
따라서 다시 주황색 부분에 해당하는 S(1,1)를 더해주면 초록색 부분의 구간합이 된다.
(sx,sy)부터 (dx,dy) 까지의 합을 Range(a,b,c,d)라고 할 때 이를 S(i,j)로 나타내면 다음과 같다.
Range(a,b,c,d)=S(dx,dy)−S(sx−1,dy)−S(dx,sy−1)+S(sx−1,sy−1)
위 수식을 이용해서 직사각형 형태의 영역의 구간합을 O(1)의 시간복잡도에 구할 수 있다.
다만 구현 시 유의해야 할 점은, 정수 오버플로에 유의해야 한다.
1차원 구간합 수열의 경우 S0=0인데,
2차원 구간합 수열의 경우 S(0,x)와 S(x,0)와 같은 형태로 나타나는 수열의 값은 모두 0이다.
따라서 해당 값에 0으로 값이 잘 들어가도록 하여 실수를 방지해야 한다.
2차원 구간합 수열을 구하는 방법은 Row 방향으로 한번 1차원 구간합을 모두 다 구한 뒤, Column 방향으로 구해진 구간합을 다시 구간합 하면 된다.
a(i,j)에서 Row(가로)방향으로 누적합을 구하여서 s(i,j) 수열이 되고, 해당 수열을 Column(세로)방향으로 누적합을 구해서 최종적인 S(i,j) 수열이 된다.
Star sky 문제 풀이 코드
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int map[101][101][11];
int main() {
int n, q, c;
cin >> n >> q >> c;
for (int i=0; i < n; i++) {
int a,b,c;
cin >> a >> b >> c;
map[a][b][c]++;
}
for (int s=0; s < 11; s++) {
for (int x=0; x < 101; x++) {
for (int y=0; y < 100; y++) {
map[x][y+1][s] += map[x][y][s];
}
}
}
for (int s=0; s < 11; s++) {
for (int x=0; x < 101; x++) {
for (int y=0; y < 100; y++) {
map[y+1][x][s] += map[y][x][s];
}
}
}
while(q--) {
int t, x1, y1, x2, y2;
cin >> t >> x1 >> y1 >> x2 >> y2;
int sum=0;
for (int src_bright = 0; src_bright < 11; src_bright++) {
int add = (src_bright + t) % (c+1);
int num = map[x2][y2][src_bright] - map[x1-1][y2][src_bright] - map[x2][y1-1][src_bright] + map[x1-1][y1-1][src_bright];
sum += add*num;
}
cout << sum << endl;
}
}
복잡도 분석
누적합을 사용하는데에는 2단계의 Step이 있다.
1. 전처리(Preprocessing) : 누적합 수열 S(i) 혹은 S(i,j)를 구한다.
2. 계산 : 원하는 구간의 구간합을 계산한다.
전처리 단계의 경우 1차원 누적합일 경우 O(N)의 시간복잡도와 공간 복잡도를 갖는다.
2차원 누적합은 전처리 단계에서 O(N2)의 시간복잡도와 공간 복잡도를 갖는다.
계산 단계의 경우 차원과 관계없이 O(1)의 상수 시간복잡도를 갖는다.
누적합의 한계
누적합의 경우에는 합을 구하는 도중에 원본 수열값이 변하는 경우 누적합 수열을 다시 계산해야하는 단점이 있다. 따라서 원본 수열값이 변할 수 있는 경우에 구간 합을 빠르게 구해야 할 경우에는 세그먼트 트리를 사용해야 한다.
