[C++] 누적 합(Prefix sum)

누적 합(Prefix sum)

계산 양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘이다.

 

1. 기본 원리

1) 1차원 배열

1차원 배열에서 i번째부터 j번째 인덱스까지 k를 더한 것을 기록하려면, 새로운 배열의 i번째 인덱스에 k를 더하고 j+1번째 인덱스에 k를 빼면 된다.

• 새로운 배열의 크기는 기존 배열 크기보다 하나 이상 크게 만든다.

 

예를 들어 크기가 5인 배열에서 0번째부터 2번째 인덱스까지 N을 빼고 싶다면 다음과 같이 누적 합 배열을 만든다.

{ -N, 0, 0, N, 0, 0 }

 

위 새로운 배열을 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다.

 

누적 합 예1

 

추가로 1번째부터 2번째 인덱스까지 M을 더하고 싶다면 누적 합 배열에 값을 추가한다.

{ -N, -M, 0, N, M, 0 }

 

다시 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다.

 

누적 합 예2

 

누적 합 배열에 계속 값을 저장한 후 마지막에 한 번만 누적 합을 계산하면, 최종적인 변화량을 기록하는 배열을 가질 수 있다.

 

2) 2차원 배열

2차원 배열 누적 합

 

2. 문제

https://programmers.co.kr/learn/courses/30/lessons/92344

코딩테스트 연습 - 파괴되지 않은 건물

#include <vector>
using namespace std;

int PrefixSum[1001][1001];

int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
    // 2차원 배열 누적합
    for (vector<int> sk : skill) {
        int degree = sk[5] * (sk[0] == 1 ? -1 : 1);
        PrefixSum[sk[1]][sk[2]] += degree;
        PrefixSum[sk[1]][sk[4] + 1] -= degree;
        PrefixSum[sk[3] + 1][sk[2]] -= degree;
        PrefixSum[sk[3] + 1][sk[4] + 1] += degree;
    }

    // 위에서 아래로 누적합
    for (int i = 0; i < board.size(); i++)
        for (int j = 1; j < board[0].size(); j++)
            PrefixSum[i][j] += PrefixSum[i][j - 1];

    // 왼쪽에서 오른쪽으로 누적합
    for (int i = 1; i < board.size(); i++)
        for (int j = 0; j < board[0].size(); j++)
            PrefixSum[i][j] += PrefixSum[i - 1][j];

    int answer = 0;
    for (int i = 0; i < board.size(); ++i)
        for (int j = 0; j < board[0].size(); ++j)
            if (board[i][j] + PrefixSum[i][j] > 0)
                answer++;

    return answer;
}