알고리즘 문제 해결 전략2 17장 부분 합(1)

17.1 도입

부분 합이란 별 것이 아니고, 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열임. scores[]의 부분 합 psum[]의 각 원소를 다음처럼 정의할 수 있음. 별 것 아닌 단순한 아이디어이지만 부분 합은 종종 아주 유용하게 이용됨.

 

부분 합 계산하기

vector<int> partialSum(const vector<int>& a) {
	vector<int> ret(a.size());
	ret[0] = a[0]
		for (int i = 1; i < a.size(); ++i)
			ret[i] = ret[i - 1] + a[i];
	return ret;
}

int rangeSum(const vector<int>& psum, int a, int b) {
	if (a == 0) return psum[b];
	return psum[b] - psum[a - 1];
}

반복문을 통해 구간 합을 구하기 위해 최대 O(N)이 걸린다는 점을 돌이켜 보면, 구간 합을 두 번 이상 구할 때는 대부분의 경우 부분 합을 사용하는 쪽이 이득임.

 

부분 합으로 분산 계산하기

rangeSum()의 결과를 b-a+1로 나누면 해당 구간의 평균을 쉽게 구할 수 있음. Quantization을 풀 때도 이런 방법을 사용헀음. 어떤 구간을 x로 근사할 때, 오차 제곱의 합은 분산과 거의 비슷한 형태의 식으로 구할 수 있음. 

 

2차원으로의 확장

psum[][]을 미리 계산해두면 2차원 배열에서도 우리가 원하는 구간의 합을 쉽게 구할 수 있음. 

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에 가장 가까운 구간

이런 구간을 찾는 한 가지 장법은 모든 구간을 순회하면서 각각의 합을 계산하는 것임. 이것은 O(N^2)임.