1314. Matrix Block Sum

https://leetcode.com/problems/matrix-block-sum/

Matrix Block Sum - LeetCode

---

2차원에서 Prefix Sum(부분합), Range Sum(구간합) 알고리즘 문제로, 간단한 1차원 Range Sum 예제는 아래와 같이 a에서부터 b까지 구하는 요청이 N개 들어오는 경우를 해결하는 방법이 있다. Sudo 코드로는 아래와 같으며, 이 경우 O(1)의 시간복잡도를 갖는다.

 

*Prefix Sum : 0 ~ a 까지의 합

*Range Sum : a ~ b 까지의 합

 

arr = [0, 1, ..., x];

preFixSumTable = [0, sumTo(1), sumTo(2), sumTo(3)..., sumTo(x)];

function preFixSum(a, b) {

    return sum[b] - sum[a];

}

 

2차원의 경우, 이미지 처리에서 많이 사용되며, 이 경우에도 O(N*M)의 시간복잡도로 구현이 가능하다. preFixSumTable의 경우, 원래 Table의 크키보다 가로, 세로가 1개 더 많게 만들어야 계산이 간단해진다.

 

아래 풀이와 관련해서, 이해가 안되는 부분이 하나 있었는데, 몇 주 지나고 다시 문제 푸니까 납득이 됐다.

 

var matrixBlockSum = function(mat, K) {
    // create DP Table matrix (m+1 * n+1)
    let dp = Array(mat.length + 1);
	// set first row value as 0
    dp[0] = Array(mat[0].length + 1).fill(0);
	
    // fill dp table with cumulative sum from (0,0) to (i,j)
    for(let i = 0; i < mat.length; i++){
        dp[i+1] = [0];
        for(let j = 0; j < mat[0].length; j++){
            dp[i+1][j+1] = mat[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j];
        }
    }
    // find sum of r, c cells (cells in square) using DP table (inclusion/exclusion)
    for(let i = 0; i < mat.length; i++){
        for(let j = 0; j < mat[0].length;j++){
            let r1 = Math.max(0, i - K), r2 = Math.min(mat.length - 1, i + K);
            let c1 = Math.max(0, j - K), c2 = Math.min(mat[0].length - 1, j + K);
            // r1++; r2++; c1++; c2++;
            mat[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1]
        }
    }
    // used mat as result matrix
    return mat;
};

위 풀이에서 두번째 for문을 돌리는 과정 중 아래 line의 코드가 이해가 안됐다.

 

mat[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1]

 

왜 많고 많은 수식 중에 저 수식인가? 라는 의문이 있었는데, range Sum을 구성하고 solution을 찾다보니 그냥 저 수식대로 해야 원하는 값을 구할 수 있어서.. 라고 보인다. rangeSum 개념을 아는 상태에서 이 문제를 처음 접하게 된다면, 저 line의 코드를 구현해내는게 정답을 가르는 열쇠이지 않을까 싶음.

 

i=0, j=0 / i=1, j=1 / i=2, j=2 인 경우들에 대해서 행렬을 아래와 같이 구해보았다.

참고

https://www.youtube.com/watch?v=KT864Aa3zE0&t=198s 

 

연관문제

304. Range Sum Query 2D - Immutable
307. Range Sum Query - Mutable
308. Range Sum Query 2D - Mutable: Premium
1738. Find Kth Largest XOR Coordinate Value

---

 

 

 

 

https://leetcode.com/problems/matrix-block-sum/discuss/513557/Javascript-DP-Solution-(beats-100.00-)

// __________________Syntax__________________

// 부등호 만들기

// let rMin = Math.max(0, i - K),

// rMax = Math.min(mat.length - 1, i + K);

// let cMin = Math.max(0, j - K),

// cMax = Math.min(mat[0].length - 1, j + K);

 

var matrixBlockSum = function (mat, K) {

  // create DP Table matrix (m+1 * n+1)

  let dp = Array(mat.length + 1);

 

  // set first row value as 0

  dp[0] = Array(mat[0].length + 1).fill(0);

  // fill dp table with cumulative sum from (0,0) to (i,j)

  for (let i = 0; i < mat.length; i++) {

    dp[i + 1] = [0];

    for (let j = 0; j < mat[0].length; j++) {

      dp[i + 1][j + 1] = mat[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j];

    }

  }

  // find sum of r, c cells (cells in square) using DP table (inclusion/exclusion)

  for (let i = 0; i < mat.length; i++) {

    for (let j = 0; j < mat[0].length; j++) {

      let r1 = Math.max(0, i - K),

        r2 = Math.min(mat.length - 1, i + K);

      let c1 = Math.max(0, j - K),

        c2 = Math.min(mat[0].length - 1, j + K);

      // r1++; r2++; c1++; c2++;

      mat[i][j] =

        dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];

      console.log(

        mat,

        dp[r2 + 1][c2 + 1],

        dp[r1][c2 + 1],

        dp[r2 + 1][c1],

        dp[r1][c1]

      );

    }

  }

  // used mat as result matrix

  return mat;

};

 

matrixBlockSum(

  [

    [1, 2, 3],

    [4, 5, 6],

    [7, 8, 9],

  ],

  1

);