99클럽 코테 스터디 21일자 TIL + count-square-submatrices-with-all-ones

문제 출처

https://leetcode.com/problems/count-square-submatrices-with-all-ones(리트코드)

학습 키워드

동적계획법

시도 방법

동적계획법을 활용한 풀이

내가 작성한 코드

class Solution {
    public int countSquares(int[][] matrix) {

        int row = matrix.length; 
        int col = matrix[0].length; 

        int[][] dp = new int[row][col]; // 원본과 똑같은 크기의 배열을 생성한다. 
        int count = 0 ; 

        //첫 행과 첫 열을 초기화한다. 

        //첫 행부분 초기화
        for(int i = 0 ; i< row ; i++) {
            dp[i][0] = matrix[i][0]; 
            count += dp[i][0]; //1인 경우 하나의 스퀘어이므로 더함 (0은 더해도 0)
        }

        //첫 열부분 초기화 (j=0은 이미 i=0으로 처리했으니까)
        for(int j = 1; j < col ; j++) {
            dp[0][j] = matrix[0][j]; 
            count += dp[0][j]; 
        }

        //dp배열 채우기 
        for(int i = 1 ; i<row; i++) {
            for(int j = 1 ; j<col; j++) {

                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; 
    
    } 
}

코드설명

예시 데이터

matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]

dp =
[
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]

//첫 행부분 초기화
for(int i = 0 ; i< row ; i++) {
    dp[i][0] = matrix[i][0]; 
    count += dp[i][0]; //1인 경우 하나의 스퀘어이므로 더함 (0은 더해도 0)
}

//첫 열부분 초기화 (j=0은 이미 i=0으로 처리했으니까)
for(int j = 1; j < col ; j++) {
    dp[0][j] = matrix[0][j]; 
    count += dp[0][j]; 
}

위 코드를 통해 matrix와 동일한 크기로 구현한 dp배열에 첫행과 첫열을 초기화한다.
이때 1인 경우는 정사각형이 하나인 경우를 의미하므로 각각 count를 더하다.

dp =
[
  [0, 1, 1, 1],
  [1, 0, 0, 0],
  [0, 0, 0, 0]
]

이후 (1,1) 부터 반복적으로 돌면서 데이터를 확인한다.

//dp배열 채우기 
for(int i = 1 ; i<row; i++) {
    for(int j = 1 ; j<col; j++) {

	 	 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]; 
          }
     }
}

예) i=1 , j=1 인 경우 matrix[i][j] == 1이므로

dp[1][1] = min(0 , 1 , 1 ) + 1 을 함으로써 1이 저장된다. 
이 뜻은 정사각형 내에 0이 하나라도 있기 때문에 크기가 2인 정사각형은 없지만 
matrix[i][j] 자체가 1이므로 크기가 1인 정사각혀잉 있으므로 1이 저장된다. 

예) i=1 , j=2 인 경우 matrix[i][j] == 1이므로

dp[1][2] = min( 1, 1, 1 ) + 1 이므로 2가 저장된다. 
이 뜻은 크기가 1인경우 자체적으로 1이 저장되며 추가적으로 크기가 2인 경우에도 
min이 1이므로 모두 1인 정사각형을 의미한다. 

예) i=1 , j=3 인 경우 matrix[i][j] == 1이므로

dp[1][3] = min( 1, 1, 1 ) + 1 이므로 2가 저장된다. 
이 뜻은 크기가 1인경우 자체적으로 1이 저장되며 추가적으로 크기가 2인 경우에도 
min이 1이므로 모두 1인 정사각형을 의미한다. 

중간 dp 데이터 체크

dp =
[
  [0, 1, 1, 1],
  [1, 1, 2, 2],   --2의 의미는 n=1일때 , n=2일때 정사각형 개수
  [0, 0, 0, 0]
]

예) i=2 , j=1 인 경우 matrix[i][j] == 1이므로

dp[2][1] = min( 1, 1, 0 ) + 1 이므로 1이 저장된다. 

예) i=2 , j=2 인 경우 matrix[i][j] == 1이므로

dp[2][2] = min( 1, 1, 1 ) + 1 이므로 1이 저장된다. 

예) i=2 , j=3 인 경우 matrix[i][j] == 1이므로

dp[2][3] = min(2 , 2 , 2 ) + 1 이므로 3이 저장된다. 
이 뜻은 n=1 일때 1개 , n=2일때 1개  , n=3일때 정사각형이 된다는 의미다. 
만약 min으로 통해 0이 나왔다면 n=2이상일때 정사각형이 성립될 수 없다. 

출력결과

dp =
[
  [0, 1, 1, 1],
  [1, 1, 2, 2],   
  [0, 1, 2, 3]    
]

새롭게 알게된 점

동적계획법..너무 어렵다.
대신 문제를 풀면서 원리를 하나하나 헤쳐가면서 풀이법을 복기하고 기억하면서
손에 익혀야겠다.

다음에 풀어볼 문제 - 입국 심사

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL