[Algorithm] 부분합 (partial sum) #230212

부분 합이란 ?

배열의 각 위치에 대해서, 배열의 시작부터 현재 위치까지의 원소의 합을 구한 배열

#include <iostream>
#include <vector>
using namespace std;

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

앞의 값에서 현재 값을 더하며 부분합 배열을 구하고, 이를 활용해서 구간 합을 위와 같이 구할 수 있다.

분산을 구할 때도 쉽게 쓰일 수 있는데, 아래와 같은 함수로 구현 가능하다

// 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);
}

sqpsum 은 A 배열의 제곱의 부분합 벡터이다.

2차원으로의 확장

#include <iostream>
#include <vector>
using namespace std;

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

이차원 배열에서 특정 그리드에 속하는 배열의 합을 구하는 과정

문제 : 크리스마스 인형 (CHRISTMAS)

이 문제는 동적 계획법으로 풀린다.

문제에서 제시된 조건은 위와 같이 수식으로 나타낼 수 있다.

위 식에 의거해서, psum 배열의 값을 mod K 까지 취한 값으로 염두에 두자면, K명의 어린이에게 똑같이 나눠주기 위해서는 psum[H-1] = psum[T]를 만족하는 H와 T를 구해야한다.

즉 psum에서 같은 숫자 집합을 모아서 2개를 선택하면 K의 배수만큼 주문을 하였다고 볼 수 있다. 이 숫자를 i이고 이 i가 psum에 출현하는 횟수를 fi라고 하자.

이 원칙을 적용해 풀 수 있다.

이 원리를 적용해서 문제를 풀기 전에, T = -1인 경우에 대해서 (H = 0) 예외를 두기 위해 psum[-1] = 0을 대입한다.

// 부분합 배열 psum과 k가 주어졌을 때 살 수 있는 방법의 가짓수를 반환한다 
int waysToBuy(const vector<int> &psum,int k) {
    int ret = 0; 
// psum에 들어가있는 숫자들의 개수를 세서 count 배열에 담는다. 
    vector<long long> count(k, 0);
    for (int i = 0; i < psum.size(); i++) {
        count[psum[i]]++;
    }
// psum에서 숫자가 2개 이상 겹치는 숫자 i에 대해서 2개 선택하는 경우의 수를 계산한다. 
    for (int i = 0; i < k; i++) {
        if (count[i] >= 2)
            ret = (ret + ((count[i] * (count[i] - 1)) / 2)) % MOD;
    }
    return ret; 
}

// 겹치지 않게 살 수 있는 가짓수를 반환한다. 
int maxBuys(const vector<int>& psum, int k) {
    vector<int> ret(psum.size(), 0);

    vector<int> prev(k, -1);
    for (int i = 0; i < psum.size(); i++) {
        if (i > 0)
            ret[i] = ret[i - 1];
        else
            ret[i] = 0;

        int loc = prev[psum[i]];
        if (loc != -1) ret[i] = max(ret[i], ret[loc] + 1);

        prev[psum[i]] = i;
    }
    return ret.back(); 
//i가 마지막인 경우에 살 수 있는 횟수를 구하면 되므로, 
// ret.back()으로 마지막 원소의 값을 구하면 해답이 된다.
}

maxBuys()에 대해 조금 더 설명하자면, ret[i]는 0부터 i번째의 인형 상자를 고려했을 때 살 수 있는 횟수를 저장한 배열이다.

prev[s]는 psum배열이 s였던 마지막 위치를 의미한다.

예를 들어서 prev[psum[0]] = prev[1] = 0; 으로 처음에 초기화되므로, psum 배열이 1이었던 마지막 위치는 0이 되는 것이다. 그러다 이미 확인한 숫자를 다시 방문하게 되면 loc에는 마지막으로 방문한 위치가 담기게 된다. 이는 loc != -1조건에 충족되므로 ret[i]에는 현재 위치와 최근에 방문한 위치에서 1을 더한 값 중에 큰 것이 담기게 된다.

현재 같은 숫자를 나타내고 있는 i와 loc = pre[psum[i]]에 대해서 최대로 주문할 수 있는 경우를 구해야 하므로 max를 사용해서 더 많이 주문할 수 있는 경우를 입력한다.

그리고 ret[i]을 이전에 구한 ret[i-1]에서 옮겨오면서 살수 있는 경우를 계속 현재와의 비교대상으로 끌어온다.