[코딩테스트] 가장 큰 정사각형 찾기 JAVA (동적 계획법 DP)

문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 있다면 가장 큰 정사각형은

1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항
표(board)는 2차원 배열로 주어집니다.
표(board)의 행(row)의 크기 : 1,000 이하의 자연수
표(board)의 열(column)의 크기 : 1,000 이하의 자연수
표(board)의 값은 1또는 0으로만 이루어져 있습니다.

입출력 예
board answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9
[[0,0,1,1],[1,1,1,1]] 4
입출력 예 설명
입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

---

이 문제는 감이 안잡혀서 검색 후 이해하고 코드를 작성해보았다. 

이 문제는 동적 계획법(DP)를 활용하여 효율적으로 풀 수 있다. 

동적 계획법(Dynamic Programming, DP)이란 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 이를 조합하여 전체 문제의 최적 해답을 찾는 방법입니다.

DP는 주로 반복되는 하위 문제가 있을 때 효과적이며,
큰 문제를 해결하는 데 필요한 중복 계산을 줄이기 위해 하위 문제의 해를 저장하고 재사용하는 것이 핵심입니다.

동적 계획법의 핵심 개념

1. 문제를 작은 하위 문제로 나누기 (분할 정복과 유사)
   문제를 풀기 위해 문제를 여러 하위 문제로 나누고, 각 하위 문제의 해를 조합하여 전체 문제를 해결합니다.
2. 중복되는 하위 문제 해결
   DP는 분할 정복법과 다르게, 반복되는 하위 문제를 해결합니다. 예를 들어 피보나치 수열처럼 같은 하위 문제가 여러 번 등장하는 경우, 계산을 반복하지 않고 한 번만 계산하여 저장해둔 후 재사용합니다.
3. 메모이제이션(Memoization)
   각 하위 문제의 해답을 저장해두고, 동일한 하위 문제를 다시 만나면 저장된 값을 재사용하여 시간 복잡도를 줄입니다.
4. 최적 부분 구조 (Optimal Substructure)
   문제의 최적 해답이 하위 문제의 최적 해답으로부터 구해질 수 있어야 합니다. 이 속성 덕분에 DP로 전체 문제의 최적 해를 찾을 수 있습니다.

예제: 피보나치 수열

피보나치 수열을 DP로 푸는 과정을 통해 이해해 보겠습니다.

피보나치 수열의 점화식

피보나치 수열은 다음과 같은 점화식을 가집니다.

F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)

여기서, F(1) = 1이고, F(0) = 0입니다.

재귀를 사용한 비효율적 풀이

피보나치 수열을 재귀로 구현하면 중복된 계산이 많아져 비효율적입니다.

 

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

동적 계획법을 사용한 효율적 풀이

중복된 계산을 피하기 위해, DP 테이블을 사용하여 이전 결과를 저장해둡니다. 이렇게 하면 시간 복잡도가 크게 줄어듭니다.

public int fibonacci(int n) {
    if (n <= 1) return n;
    
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

이 코드에서는 반복문을 사용해 피보나치 수열을 계산하며, 이미 계산한 값을 dp 배열에 저장하므로 **시간 복잡도는 O(n)**으로 줄어듭니다.

---

현재 칸을 포함해 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 위쪽, 왼쪽, 왼쪽 대각선 위 칸의 최소값 + 1입니다.

0 chk[i-1][j-1]	0 chk[i-1,j]	1
1 chk[i][j-1]	1 (기준 chk[i,j] )	1
1	1	1

0, 0 , 1 중에 최솟값은 0이다.

그럼 만들 수 있는 정사각형이 0일까? 

기준이 되는 곳이 1이니까 1의 정사각형을 만들 수 있으므로 최소값에서 +1을 해줘야한다.

다만, 기준점이 0이면 안되고 기준점으로부터 왼쪽 위쪽 왼쪽위에 부분을 봐야 하므로 x,y열의 첫째줄을 제외하고 시작해야한다.

이 계산한 값은 주어진 배열과 같은 조건의 2차원 배열(dp)을 만들어 저장한다.

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

dp 값을 보면 더해진 값으로 이루어져 있는 것을 알 수 있다. 

import java.util.*;

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        
        int xlen = board.length;
        int ylen = board[0].length;

        int[][] chk = new int[xlen][ylen];
        
        for(int i=0; i<xlen; i++){
            for(int j=0; j<ylen; j++){
                if(i==0 || j==0){
                    chk[i][j] = board[i][j];
                }else if(board[i][j] == 1){
                    chk[i][j] = Math.min(Math.min(chk[i-1][j],chk[i][j-1]),chk[i-1][j-1]) +1;
                    //chk[i][j] = Arrays.stream(new int[]{chk[i-1][j],chk[i][j-1],chk[i-1][j-1]}).min().getAsInt() +1;
                }
                answer = Math.max(answer, chk[i][j]);
            }
        }

        answer *= answer;
        return answer;
    }
}

 

가장 긴 변의 길이를 구했으므로 마지막에 제곱 해준다. 

---

여러개 숫자의 최솟값 구하기 

chk[i][j] = Math.min(Math.min(chk[i-1][j],chk[i][j-1]),chk[i-1][j-1]) +1;

Math.min으로 세 개의 숫자의 최솟값을 구하려면 2개를 먼저 비교하고, 남은 하나를 그 값과 비교해야한다.

하지만 JAVA8부터는 Arrays.stream을 활용하면 한꺼번에 비교할 수 있다.

chk[i][j] = Arrays.stream(new int[]{chk[i-1][j],chk[i][j-1],chk[i-1][j-1]}).min().getAsInt() +1;

하지만 이 방법을 쓰니 시간초과가 떠서 효율성이 떨어져 보이므로 Math.min의 방법을 추천한다.