[종만북] 부분 합

N명의 시험 성적이 내림차순으로 저장되어있는 배열 score이 있다고 할때 a등에서 b등까지 평균점수를 계산하자

평균점수를 계산할때는 score[a]에서 score[b]까지 더하고 b-a+1를 나누면 됩니다. 하지만 이 방법은 O(N)이 걸리게 됩니다.

 따라서 부분합 배열 Sum을 사용하면 O(1)에 문제를 해결할 수 있습니다.

	0	1	2	3	4	5	6	7	8
score	1	2	3	4	5	6	7	8	9
sum	1	3	6	10	15	21	28	36	45

부분합을 구현하는 함수는 다음과 같습니다

vector<int> partialSum(vector<int> score){
	vector<int>ret;
    int temp=0;
	for(int i=0;i<score.size();i++){
    	temp+=score[i];
    	ret.push_back(temp);
	}
}

부분합을 계산하는데는 선형시간이 걸립니다. 하지만 이를 이용해 선형합을 구하는데는 O(1)만 걸리므로 여러번 부분합을 구할 때는 부분합을 구현하는게 이득입니다.

 

부분합 배열을 이용해 계산하는 함수는 다음과 같습니다. a부터b까지 합을 구하는 함수입니다.

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

 

2차원에서 부분합 사용하기

 

2차원 배열 A[][]이 있을때, A[y1][x1]에서 A[y2][x2]의 구간의 합을 구할때는 부분합 psum[][]을 사용하면 편합니다

sum[x1,y1,x2,y2]=psum(y2,x2)-psum(y2,x1-1)-psum(y1-1,x2)+psum(y1,y2)

 

int gridSum(vector<vector<int>> psum, int x1, int y1, int x2, int y2){
	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][x1];
    
    return ret;
}

 

예제 합이 0에 가장 가까운 구간

 

양수와 음수가 모두 포함한 배열에서 그 합이 0에 가장 가까운 구간을 찾는 문제입니다.

 

i	0	1	2	3	4	5	6	7	8
A[i]	-14	7	2	3	-8	4	-6	8	9

 

합이 0에 가장 가깝다는 말은 부분합 psum[]의 두 값의 차이가 가장 작다는 말입니다.

따라서 psump[]을 정렬하고 인접한 원소들을 모두 확인하면 O(NlogN)에 해결할 수 있습니다.

정렬에 O(logN) 이걸리고, 인접한 원소를 확인하는데 O(N)이 걸리기 때문입니다.

 

부분합을 사용하지 않는다면 모든 구간을 탐색해야 하므로 O(N^2)이 걸리게 됩니다.