이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.
부분 합(partial sum, prefix sum)
= 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해둔 배열
= 누적 합(cumulative sum)
부분 합을 미리 계산해 두면 특정 구간의 합을 O(1)에 구할 수 있다
//주어진 벡터 a의 부분 합을 계산한다
vector<int> partialSum(const vector<int>& a){
vector<int> ret(a.size());
ret[0] = 0;
for(int i = 1; i< a.size(); ++i)
ret[i] = ret[i-1] + a[i];
return ret;
}
//어떤 벡터의 부분합 psum이 주어질 때
//원래 벡터의 a부터 b까지의 합을 구한다
int rangSum(const vector<int>& psum, int a, int b){
if(a == 0) return psum[b];
return psum[b] - psum[a-1];
}
//A[]의 제곱의 부분 합 벡터 sqpsum와 A[]의 부분 합 벡터 psum이 주어질 때
//A[a..b]의 분산을 반환한다
double variance(const vector<int>& sqpsum, const vector<int>& psum, int a, int b){
//해당 구간의 평균 계산
double mean = rangeSum(psum, a, b) / double(b-a+1);
//해당 구간의 분산 계산
double ret = rangeSum(sqpsum, a, b) - 2 * mean * rangeSum(psum, a, b) + (b - a + 1) * mean * mean;
return ret / (b - a + 1);
}
2차원 배열에서도 부분 합을 사용할 수 있다
2차원 배열 A [ ][ ] 의 부분 합
-> psum[y,x]: (0,0)을 왼쪽 위 칸, (y,x)를 오른쪽 아래 칸으로 갖는 직사각형 구간에 포함된 원소들의 합
//어떤 2차원 배열 A[][]의 부분합 psum[][]이 주어질 때,
//A[y1,x1]과 A[y2, x2]를 양끝으로 갖는 부분 배열의 합 반환
int gridSum(const vector<vector<int>>& psum, int y1, int x1, int y2, int x2){
int ret = psum[y2][x2];
if(y1>0) ret -= psum[y1-1][x2];
if(x1>0) ret -= psum[y2][x1-1];
if(y1>0 && x1>0) ret += psum[y1-1][x1-1];
return ret;
}
양수와 음수가 모두 포함된 배열 A[]이 있을 때, 그 합이 가장 0에 가까운 구간을 찾는 문제
A의 모든 구간을 순회하면서 각각의 합을 계산하는 방법
-> 배열의 길이 N에 대해 O(N^2)의 시간 복잡도
부분 합을 이용하면 O(NlogN)의 시간 복잡도로 해결 가능하다
A[i] ~ A[j] 구간의 합 = psum[j] - psum[i-1]
-> 구간의 합이 0에 가까운 경우 찾기
-> psum[j]과 psum[i-1]의 값의 차이가 가장 작은 경우 찾기
-> psum[] 배열을 정렬한 뒤 인접한 원소들을 확인한다
psum[]을 정렬하여 인접한 원소를 확인하는 이유?
- 어떤 수의 집합을 각 수의 크기로 정렬을 하게 되면, 서로 인접한 숫자는 그 집합의 어떤 숫자와 비교하더라도, 인접한 두수의 차이가 가장 적게 된다
- 이 특성을 활용해서, min(psum[i] - psum[i-1])이 최소가 되는 값을 찾으면, 합이 0에 가장 가까운 구간합을 찾을 수 있다
O(NlogN)의 시간 복잡도?
- O(N): 구간 합을 계산할 때 걸리는 시간 복잡도
- O(NlogN): psum을 정렬하는데 걸리는 시간 복잡도
- O(N): 정렬된 psum에서 0에 가장 가까운 구간합을 찾을 때 걸리는 시간 복잡도
-> 따라서, O(N)은 없어지고 보다 큰 시간 복잡도인 O(NlogN)만 남는다