99클럽 코테 스터디 16일차 TIL - DP

오늘의 학습 키워드

DP

---

알고리즘 문제

• LeetCode Medium. 1277. Count Square Submatrices with All Ones
• https://leetcode.com/problems/count-square-submatrices-with-all-ones/

---

공부한 내용

DP

 

Math.min(Math.min(A, B), C) 

• A, B, C 중에 제일 작은 수

---

오늘의 회고

처음 시도

• 작은 정사각형부터 검사해서 더 큰 정사각형을 찾기 위해 시도했다. 
• DP로 풀기 위해 dp[][] 배열을 두고 정사각형을 찾을 때마다 숫자를 더해주는 방식이어야 한다고 생각했다.
• 내가 생각하지 못했던 부분은 정사각형 크기 결정 기준 지점이다. 나는 처음에 정사각형이 시작하는 지점을 기준으로 정사각형을 정의했기 때문에 DP 배열을 재사용할 수 있는 방법을 찾기 못했다.

해결

• 해결점은 정사각형이 끝나는 지점을 기준으로 생각해야 했다.
• 첫번째 행과 첫번째 열은 그대로 dp 배열에 넣는다.
  => 첫 행과 첫 열은 그대로 정사각형을 이루기 때문에 dp에 바로 넣는다.
• 그 외에 위치들은 현재 위치 값이 0이 아니면, 1X1 보다 큰 정사각형을 만들 수 가능성이 있기 때문에 비교해서 dp 배열을 변경한다.
• 즉, 현재 위치 중심으로 가장 큰 정사각형 크기를 알아보는 방법은 현재 위치에서 왼쪽, 대각선 왼위쪽, 위쪽 위치에서 가능한 정사각형 크기 중 가장 작은 값을 찾아서 +1 하면 현재 위치가 새로운(현재까지 가장 큰) 정사각형의 오른쪽 아래 모서리가 되는 위치를 나타낸다.
  • 예를 들어, (1,1) 지점의 값이 0이 아니면 왼쪽(1,0), 위쪽(0,1), 왼쪽위대각선(0,0) 값 중에 최솟값을 찾는다.
  • 그 다음으로, 최솟값에 +1을 하면 만들 수 있는 최대 정사각형 크기가 나온다.
    => 위, 왼, 위왼대각선 이 3개의 값들은 정사각형을 만드는 좌표이기 때문이다.
  • dp 배열의 해당 위치에 위치 값이 0인 경우 0을, 1인 경우 최솟값+1을 넣는다.
• 결과적으로 모든 dp 값을 더하면 총 정사각형 개수가 나온다.

---

문제 풀이

class Solution {
    public int countSquares(int[][] matrix) {
        int xlen = matrix[0].length;
        int ylen = matrix.length;
        int[][] dp = new int[ylen][xlen];
        int count = 0;

        for (int i = 0; i < ylen; i++) {
            for (int j = 0; j < xlen; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 1) {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                }
                count += dp[i][j];
            }
        }

        return count;
    }
}