누적합 (Prefix Sum)

말 그대로 구간의 누적합을 구하는 문제입니. 지정된 인덱스부터 하나하나 더하는 방식은 최악의 경우 O(n^2) 의 시간복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(n) 으로 해결할 수 있다.

예를 들어, 크기가 5인 배열에서 인덱스가 2 ~ 5인 구간의 합을 구한다고 가정하면, 누적합은 5의 누적합 - 2의 누적합 으로 간단하게 구할 수 있습니다. 도식화 해보자면

index	0	1	2	3	4	5
sum	0	1	3	6	10	15

인덱스가 2 ~ 5인 구간의 인덱스의 합을 구하는 것을 생각해보면,
5의 누적합에서 빼야 할 부분은 0~1 인 구간이고, 이는 1의 누적합이 됩니다. 따라서 정답은 5의 누적합에서 1의 누적합을 뺀 15 - 1 = 14 가 됩니다. 한마디로

누적합에서 중복되는 부분을 빼고 빈 부분을 더하자

라고 표현할 수 있습니다. 2차원을 예로들어 보면

y\x	0	1	2	3
0	0	1	2	3
1	1	4	8	13
2	2	8	16	26
3	3	13	26	42

표를 채우는, 누적합을 구하는 점화식은

dp[x][y] = dp[x][y-1] + dp[x-1][y] - dp[x-1][y-1] + ( x + y )

가 됩니다. 이 점화식으로 구한 위와 같은 표에서 (1,1) ~ (3,3) 까지 정사각형 부분의 인덱스의 합을 구하는 문제가 있다고 한다면, 우선

(3,3) 의 누적합 = 42

입니다. 이때 더해지면 안되는 부분들이 더해지게 됩니다. 바로 (0,0) ~ (3,0) 과 (0,0) ~ (0,3) 입니다. 이 부분은 문제에서 요구하는 범위가 아니지만, (3,3) 의 누적합에는 더해져 있습니다. 따라서 해당하는 부분의 누적합을 빼줘야 합니다. 따라서

(3,3) - (0,3) - (3,0)

가 나옵니다. 하지만 여기서 (0,0) 은 두번 (0,3)과 (3,0)에서 두 번, 중복되서 빼지므로 한번 더해줘야 합니다. 따라서 최종적인 누적합은

(3,3) - (0,3) - (3,0) + (0,0)

이 됩니다. 이를 정리하자면 2차원 공간에서의 누적합은

dp[to][to] - dp[from-1][to] - dp[to][from-1] + dp[from-1][from-1]

이 됩니다. 결국 위에서 했던 전체에서 중복되는 부분을 빼고 2번 빼진 부분은 더하고를 반복하는 과정입니다. 집합의 연산과 똑같습니다.

25682 - 체스판 다시 칠하기2

이 방식으로 푸는 문제가 바로 25682번 - 체스판 다시 칠하기2 문제 입니다. 25682 - 체스판 다시 칠하기2

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


int calculation(char standard, int n, int m, int k, vector<vector<char>> stage) {
    vector<vector<int>> table (n + 1, vector<int> (m + 1, 0));

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            int value = 0;
            if ((x + y) % 2 == 0) value = (stage[x][y] != standard);
            else value = (stage[x][y] == standard);

            table[x + 1][y + 1] = table[x][y + 1] + table[x + 1][y] - table[x][y] + value;
        }
    }

    int count = n * m / 2;
    for (int x = 1; x < n + 2 - k; x++) {
        for (int y = 1; y < m + 2 - k; y++) {
            int ps = table[x + k - 1][y + k - 1] - table[x + k - 1][y - 1] - table[x - 1][y + k - 1] + table[x - 1][y - 1];
            count = min(count, ps);
        }
    }
    return count;
}

int main(void) {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector<char>> stage;
    for (int x = 0; x < n; x++) {
        vector<char> temp;
        for (int y = 0; y < m; y++) {
            char input;
            cin >> input;
            temp.push_back(input);
        }
        stage.push_back(temp);
    }

    int answer = min(calculation('W', n, m, k, stage), calculation('B', n, m, k, stage));
    cout << answer << endl;
    return 0;
}

위 코드에서 표 전체를 탐색하며 각 인덱스에 해당하는 누적합을 구하는 방법은 다음과 같습니다.

for (int x = 0; x < n; x++) {
    for (int y = 0; y < m; y++) {
        int value = 0;
        if ((x + y) % 2 == 0) value = (stage[x][y] != standard);
        else value = (stage[x][y] == standard);

        table[x + 1][y + 1] = table[x][y + 1] + table[x + 1][y] - table[x][y] + value;
    }
}

업데이트할 칸의 위쪽, 왼쪽 칸의 누적합을 더한 후, 왼쪽상단 대각선의 누적합을 빼고 업데이트할 칸의 값을 더해줍니다. 다음으로 길이 K인 정사각형의 누적합을 구해야 하므로

table[x + k - 1][y + k - 1] - table[x + k - 1][y - 1] - table[x - 1][y + k - 1] + table[x - 1][y - 1]

위 점화식을 사용하였습니다. 정사각형을 생각해 보았을 때, 오른쪽 하단의 인덱스는 (x + k-1, y + k-1) 이므로 해당하는 곳의 누적합에서 왼쪽 하단의 누적합과 오른쪽 상단의 누적합을 빼고 기준점의 누적합을 더하면 정사각형의 누적합이 나오게 됩니다.

구간의 합을 유동적으로 구해야 하는 경우 매우 빠르게 구할 수 있는 알고리즘 인 것 같습니다.