[종만북] 17장 부분합

종만북 17장 부분합

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-07-12

• 부분 합(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];
}

부분 합으로 분산 계산하기

• 분산(variance): 편차 제곱의 평균

//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차원 배열에서도 부분 합을 사용할 수 있다

• 2차원 배열 A [ ][ ] 의 부분 합
  -> psum[y,x]: (0,0)을 왼쪽 위 칸, (y,x)를 오른쪽 아래 칸으로 갖는 직사각형 구간에 포함된 원소들의 합

• A[y1, x1]에서 A[y2, x2] 까지의 직사각형 구간의 합
  -> psum[y2, x2] - psum[y2, x1-1] - psum[y1-1, x2] + psum[y1-1, x1-1]

//어떤 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;
}

합이 0에 가장 가까운 구간

• 양수와 음수가 모두 포함된 배열 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[] 배열을 정렬한 뒤 인접한 원소들을 확인한다

📌참고자료

• 합이 0에 가장 가까운 구간의 합
  https://skysign.tistory.com/190
  https://jaimemin.tistory.com/486

psum[]을 정렬하여 인접한 원소를 확인하는 이유?

• 어떤 수의 집합을 각 수의 크기로 정렬을 하게 되면, 서로 인접한 숫자는 그 집합의 어떤 숫자와 비교하더라도, 인접한 두수의 차이가 가장 적게 된다
• 이 특성을 활용해서, min(psum[i] - psum[i-1])이 최소가 되는 값을 찾으면, 합이 0에 가장 가까운 구간합을 찾을 수 있다

O(NlogN)의 시간 복잡도?

• O(N): 구간 합을 계산할 때 걸리는 시간 복잡도
• O(NlogN): psum을 정렬하는데 걸리는 시간 복잡도
• O(N): 정렬된 psum에서 0에 가장 가까운 구간합을 찾을 때 걸리는 시간 복잡도
  -> 따라서, O(N)은 없어지고 보다 큰 시간 복잡도인 O(NlogN)만 남는다