누적합 알고리즘 (2022 카카오 - 파괴되지 않은 건물)

해당 문제는 정확성과 효율성을 모두 고려해야하는 문제이기 때문에 매 스킬마다 해당하는 구간을 계산하면 O(KNM)의 시간 복잡도가 나오게 되어 실패한다.

그래서 처음 생각했던 방법은 큐를 만들어 치유인 경우에는 큐에 더하고 파괴 스킬일 때 큐를 먼저 차례대로 실행 후 파괴하면 어떨까 했는데 효율성에서 1개 빼고 모두 시간초과가 떴다..

혼자서는 방법을 못찾겠어서 찾은 방법이 누적합 알고리즘

누적합 알고리즘은 알고리즘 이름대로 나열된 수(구간)의 합을 구하는 알고리즘이다. 다만, 이전처럼 매번 모든 구간에 합을 적용하는 방식이 아니다.
문제는 2차원이지만 1차원에서부터 시작한다면..

방식은 간단하다. 구간 [i..j] 까지 n을 더하면 arr[i] = n, arr[j+1] = -n 값을 넣는 방식으로 계산들을 누적해서 적용한 후에 마지막에 한꺼번에 계산하는 방식이다. j+1 번째에는 -n 을 넣었으므로 i..j+1까지 직전 칸의 값을 더하면(합이 누적되면) 원하는 구간에 합이 제대로 적용되는 원리이다.

복잡하다. 예를 들자면 크기가 7인 배열에 1번째 ~ 4번째에 3을 더한다고 했을 때, arr[1] = 3, arr[5] = -3 값이 들어간다.

왼쪽에서 오른쪽으로(j+1 번째에 -n 값을 넣었기 때문에) 누적합을 진행하면 아래와 같이 차례대로 더해지면서 의도한 구간에 합이 진행되었다.

이 경우는 계산을 한번만 하기 때문에 간단해보이지만, 계산이 여러개 있고, 구간이 겹치면서부터 헷갈려졌다.
1. [1...4] +3
2. [5...6] -4
3. [3...5] 3
를 한다면?

1. [1...4] +3 첫번째 그림과 같다.
2. [5...6] -4

3. [3...5] 3

1~3 구간 작성(?)을 진행했으니까 전체 누적합을 구하면 된다. 직전 칸의 값이랑 합하면서 진행한다.

 이렇게하면, 1~3 계산이 원하는대로 적용되었지만 나는 어떻게 이렇게 하면 누적합이 구해질 수 있는건지 잘 이해가 안갔다. 직전 칸과 자기 자신 칸을 더하고... 특히 어떻게 j+1에 -n 을 넣으면 상쇄되는지?
그래서 a,b,c로 겹치는 구간을 만들어서 해보니 훨씬 이해가 잘 갔다.

a,b,c 값이라고 가정

 

누적합

원리를 이해하고 나면 2차원도 간단하다. 다만 1차원에서는 j+1 번째에만 -n을 했다면 [i][j] ~ [ii][jj] 구간을 나타내기 위해서는 세 군데 범위 제한이 필요하다.

• arr[i][jj+1] = -n
• arr[ii+1][j] = -n
• arr[ii+1][jj+1] = n

누적합을 구할 때는 규칙만 잘 정하면 된다. 왼-오 & 위-아래로 할 지, 위-아래 먼저 누적합을 구하고 왼-오로 진행할 지 등..

제출한 코드:

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int N = board.length;
        int M = board[0].length;
        int[][] cumSum = new int[N+1][M+1];

        for (int[] cur: skill) {
            int minY = cur[1];
            int minX = cur[2];
            int maxY = cur[3] + 1;
            int maxX = cur[4] + 1;
            int degree = cur[5] * (cur[0] == 1 ? -1 : 1);
            int minusDegree = degree * -1;
            cumSum[minY][minX] += degree;
            cumSum[minY][maxX] += minusDegree;
            cumSum[maxY][minX] += minusDegree;
            cumSum[maxY][maxX] += degree;
        }

        // LEFT =====> RIGHT
        for (int i = 0; i < N + 1; i++) {
            for (int j=1; j < M + 1; j++) {
                cumSum[i][j] += cumSum[i][j-1];
            }
        }

        // TOP ======> BOTTOM
        for (int j=0; j < M + 1; j++) {
            for (int i = 1; i < N + 1; i++) {
                cumSum[i][j] += cumSum[i-1][j];
            }
        }

        for (int i=0; i < N; i++) {
            for (int j=0; j < M; j++) {
                board[i][j] += cumSum[i][j];
                if (board[i][j] > 0)
                    answer++;
            }
        }
        return answer;
    }
}