부분합(partial sum)

알고리즘 스터디

부분합(partial sum)

17.1 도입

• N 명의 시험 성적을 내림차순 으로 정렬해준 배열 scores[]가 있을 때 평균 average(a, b)를 구한다고 하자. 일반적인 방법은scores[a]~scores[b] 를 더한 뒤 이것을 b-a+1로 나누는 것이다. 이렇게 하면 반복문의 수행 횟수를 최대 O(N)이 된다.
• 평균 점수를 한 번 계산할 거라면 이걸로 충분하지만 여러 번 호출하게 될 거라면 이것을 좀 더 최적화 할 수 없나 생각하게 된다.
• 이럴때 유용하게 사용되는 것이 부분합(partial sum) 이다.

부분합은은 다음 처럼 정의 할 수 있다.

psum[i] = ∑(j=0,i)scores[j]

다음 표는 한 예제 배열 scores[]의 각 원소와 해당 배열의 부분합을 보여준다.

i	0	1	2	3	4	5	6	7	8
score	100	97	86	79	66	52	49	42	31
psum	100	197	283	362	428	480	529	571	602

psum을 미리 계산해 두면 scores[]의 특정 구간의 합을 O(1)에 구할 수 있다. scores[a]부터 scores[b]까지의 합을 다음과 같이 얻으면 된다.

psum(b) - psum(a-1)

• 단순한 아이디어지만 부분 합은 종종 아주 유용하게 이용된다.

부분합 계산하기

• 구간합을 빠르게 계산하기 위해 구간 합을 미리 계산해 둔다.
• 아래 코드 17.1의 partialSum()은 구간합을 미리 구하는 예제이다.
• 반복문을 통해 구간 합을 구하기 위해 최대 O(N)의 시간이 걸린다는 점을 돌이켜 보면, 구간합을 두 번 이상 구할 때는 대부분의 경우 부분합을 사용하는 편이 이득임을 알 수 있다.

부분 합 계산하기

코드 17.1 부분합을 계산하는 함수와 이를 이용해 구간을 계산하는 함수의 구현

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];
}

부분 합으로 평균 계산하기

• 코드 17.1 의 rangeSum()은 특정 구간은 O(1)로 계산한다. rangeSum()의 결과를 b-a+1로 나누면 해당 구간의 평균을 쉽게 구할 수 있다.

1/(b-a+1) * rangeSum(psum, a,b)

부분 합으로 분산(variance) 계산하기

• 배열 A[]의 구간 A[a … b] 의 분산은 다음과 같은 식으로 정의된다.

v = 1 / (b-a+1) * ∑ (i=a,b) (A[i] - m(a,b))^2

• m(a,b)는 해당구간의 평균이다.
• 이것만으로 분산을 계산하기는 힘들다. 그러나 이 식을 다음과 같이 정리해보자

v = 1/(b-a+1) * ∑ (i=a,b) (A[i] - m(a,b))^2 
= 1/(b-a+1) * ∑ (i=a,b) (A[i]^2 - 2A[i] *m(a,b) + m(a,b)^2) 
= 1/(b-a+1) * ( ∑ (i=a,b)A[i]^2 - 2m(a,b)* ∑ (i=a,b)A[i] + (b-a+1)m(a,b)^2)

• 이때 괄호안의 세계의 항 중, 가운데 항과 오른쪽 항은 psum을 이용해 쉽게 계산 할 수 있다. 문제가 되는 것은 A[i]^2의 합인데, 이것 또한 A[]의 각 제곱의 부분합을 저장하는 배열을 미리 만들어 두면 O(1)에 계산 할 수 있다.

코드 17.2 배열의 부분합과 제곱의 부분합을 입력받고 특정 구간의 분산을 계산하는 함수의 구현

    // 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[][]이 주어질 때, A[y1,x1] 에서 A[y2,x2]까지의 직사각형 합은 다음과 같이 부분합 배열을 사용해 빠르게 구할 수 있다.

psum[y,x] = ∑(i=0,y)∑(j=0,x)A[i,j]

• 다시 말해 psum[y,x]는 (0,0)을 위쪽 위칸, (y,x)를 오른쪽 아래 칸으로 갖는 직사각형 구간에 포함된 원소들의 합이다.
• psum[][]을 미리 계산해 두면 2차원 배열 에서도 우리가 원하는 구간의 합을 아래 식과 같이 쉽게 구할 수 있다.

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

코드 17.3 부분 합을 이용해 2차원 배열의 구간 합을 구하는 함수의 구현

    // 어떤 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[]가 있을 때, 그 합이 가장 가까운 구간을 찾는 문제를 풀어 보자.

i	0	1	2	3	4	5	6	7	8	9
a[j]	-14	7	2	3	-8	4	-6	8	9	11

• 0에 가장 가까운 구간은 A[2]~A[5]로 그 합은 1이다.
• 이런 구간을 찾는 한 가지 방법은 A의 모든 구간을 순회하면서 각각의 합을 계산하는 것이다.
• 이렇게 하면 배열 길이 N에 대해 O(N^2)의 시간이 걸린다.
• 부분합 을 사용하면 이 분제를 아주 쉽게 풀 수 있다.
• A[i] ~ A[j]의 구간의 합을 다음과 같이 표현 할 수 있다.

∑(k=i, j)A[k] = psum[j] - psum[i-1]

• 이 값이 0에 가깝다는 말은 psum[]의 두 값의 차이가 가장 적다는 뜻이다.
• 주어진 배열에서 가장 가까운 두 값을 찾기 위한 간단한 방법은 이 배열을 정렬한 뒤 인접한 원소들을 확인하는 것이다.
• 정렬은 O(NlgN)시간에 수행할 수 있다.
• i-j의 구간 합 계산은 O(NlgN)시간에 수행할 수 있다.
• 부분합을 구하는 것과 인접한 원소들을 확인하는 것 모두 O(N)에 할 수 있으니 이 알고리즘 수행시간은 O(NlgN) 이 된다.

코드 17.4 합이 0에 가장 가까운 구간을 찾는 코드

    # python으로 구현됨
    # 부분합 배열 구함
    psum = partialSum(list)

    # 구간합 구하기
    sum = rangeSum(psum, 0, list.__len__()-1)

    len =  list.__len__() - 1
    rangelist = []

    for i in range( len ):
        for j in range( len )[i+1:]:
            rsum = rangeSum(psum, i, j)
            # 구간 최소 값과 인덱스 저장
            rangelist.append([abs(rsum),i,j])

    rangelist.sort()

    # 구간 최소값과 인덱스 출력
    print(rangelist[0])

출저 : 알고리즘 문제 해결 전략