<Algorithm> 215. 가장 큰 정사각형 찾기(Programmers)

1. 가장 큰 정사각형 찾기(Programmers)

   사용 알고리즘 :  DP

• 예전에 기업 코딩 테스트볼때 이것보다 어렵지만 비슷한 유형의 문제를 본적있다. (그때는 못풀었다...) 

• 코드를 보면 간단하지만 DP에 대한 접근방식을 모르면 상당히 어려울 수 있는 문제라 생각이 든다.

문제에 대한 접근&생각

1. 최대 넒이를 가지는 정사각형의 크기 -> n과 m은 최대 1000 -> 너무 많은 경우의 수 발생 -> DP!
2. 임의의 한점을 선택 -> 그 점을 오른쪽 아래로 가진다면?  -> 인접한 왼쪽, 위쪽, 대각선 지점에서의 최대치의 최소값으로 알 수 있음
3. 아래 그림에서 셋중에서 가장 작은 (회색영역 + 1) * (회색영역 + 1)로 크기가 정해지는 것을 알수 있음 

  

코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution {              public int solution(int[][] board){         int n = board.length;         int m = board[0].length;         int[][] dp = new int[n+1][m+1];         int max = 0;         /***************************          * DP를 활용하여 임의의 점을 기준으로          * 왼쪽,위쪽,대각선 방향으로 가능한          * 정사각형의 최대값을 저장한다.          ***************************/         for(int i = 1; i < n+1; i++) {             for(int j = 1; j < m+1; j++) {                 if(board[i-1][j-1] == 1) {                     dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]))+1;                     // +1은 해당 지점의 크기를 가리킨다.                     max = Math.max(dp[i][j], max);                 }             }         }         return max*max;     }      }   Colored by Color Scripter

cs

참고 & 출처  

https://programmers.co.kr/learn/courses/18/lessons/847