가장 큰 정사각형 찾기 ( DP 알고리즘 )

 

[ 해결 방법 ] 

1. DP 알고리즘 활용

2. 위치한 값이 1일 때, [ 왼쪽 / 왼쪽 위 대각선 / 위쪽 ] 의 값을 확인해 가장 작은 값에 +1 해준다.

 

 

 

DP 알고리즘

 

- DP 사용 조건

1) 겹치는 부분 문제 : 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

 

ex. 이진 탐색과 피보나치 수열

이진 탐색 : 정렬된 배열 내에서 그 위치를 바로 찾기 때문에 재사용 과정을 거치지 않아 DP 사용 조건에 해당하지 않는다.

피보나치 수열 : f(n) = f(n-1) + f(n-2) 이므로, 트리구조로 동일한 부분 문제가 중복되어 나타나 DP 사용 조건에 해당한다.

 

2) 최적 부분 구조 : 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

 

ex. 최적 경로 문제

여러 경로 중 [ A-X, X-B ] 가 가장 짧은 경로라면 A-X-B 가 정답이 된다.
이와 같이 부분 문제의 최적의 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않는 경우 DP를 사용할 수 있다.

 

- DP 사용 과정

1) DP로 풀 수 있는 문제인지 확인

 

2) 변수 간 점화식 만들기

 

3) Memoization

: 변수의 값에 따른 결과를 저장하는 것을 메모라고 부른다. 보통 배열을 사용하며, 1~3차원 배열이 될 수 있다.

 

5) 기저 상태 파악하기

: 가장 작은 문제의 상태를 파악해야 한다.

 

6) 구현하기

Bottom-Up ( 반복문 - Tabulation )
아래에서부터 계산을 수행해 누적시켜 전체 큰 문제를 해결하는 방식

Top-Down ( 재귀 - Memoization )
위에서부터 바로 호출하며 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

 

 

 

[ 문제 코드 ]

 

- Tabulation 방식으로 해결

 

public class 가장큰정사각형찾기 {

    /**
     * TODO
     *  - 목표: 가장 큰 정사각형을 찾아라
     *  - DB 알고리즘 활용
  장  * **/

    public static void main(String[] args) {
        int[][] arr = {{0, 0, 1, 1}, {1,1,1,1}};
        int solution = solution(arr);
        System.out.println(solution);
    }

    public static int solution(int [][]board)
    {
        int answer = 0;

        int[][] map = new int[board.length + 1][board[0].length + 1];

        int maxLen = 0;
        for (int i = 1; i <= board.length; i++) {
            for (int j = 1; j <= board[0].length; j++) {
                if(board[i-1][j-1] != 0) {
                    int min = Math.min(Math.min(map[i - 1][j], map[i][j - 1]), map[i - 1][j - 1]);
                    map[i][j] = min + 1;

                    maxLen = Math.max(maxLen, min + 1);
                }
            }
        }

        return maxLen * maxLen;
    }
}