자바 코딩테스트 강좌, 가장 큰 정사각형 찾기

문제 설명

2차원 배열이 주어졌을 때, 1로 구성된 가장 큰 정사각형의 넓이를 구하는 문제입니다. 배열의 각 요소는 0 또는 1의 값을 가지며, 1은 해당 위치가 채워져 있음을 나타냅니다. 예를 들어, 다음과 같은 배열이 주어졌다고 가정해 보겠습니다:

    0  1  1  0
    1  1  1  1
    0  1  1  0
    0  1  1  1
    

이 경우 가장 큰 정사각형의 크기는 3이며, 넓이는 9입니다.

입력 형식

입력은 m x n 크기의 2차원 배열로 주어집니다. 이 배열에서 i번째 행, j번째 열의 값이 배열의 셀을 나타냅니다.

출력 형식

가장 큰 정사각형의 넓이를 정수로 반환합니다.

접근법

이 문제는 동적 프로그래밍(Dynamic Programming)을 이용하여 해결할 수 있습니다. 동적 프로그래밍의 기본 아이디어는 이전에 계산된 결과를 사용하여 새로운 결과를 효율적으로 계산하는 것입니다. 다음과 같이 진행됩니다:

1. 새로운 2차원 DP 배열을 생성합니다. DP[i][j]는 (i, j) 위치에서 정사각형의 최대 변의 길이를 나타냅니다.
2. 배열의 요소를 순회하며, 만약 matrix[i][j]가 1이라면, DP[i][j]는 다음의 수식을 따릅니다:

DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1

3. 단, i와 j가 0일 때는 DP[i][j]는 matrix[i][j]의 값과 같아야 합니다.
4. 최대 변의 길이를 기억하고, 이를 통해 최대 넓이를 계산합니다.

구현

public class LargestSquare {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        
        int maxSide = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1; // 첫 행 또는 첫 열
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        
        return maxSide * maxSide;
    }
}

    

시간 복잡도

이 알고리즘의 시간 복잡도는 O(m * n)입니다. 여기서 m은 행의 수, n은 열의 수입니다. 배열을 한 번 순회하기 때문에 매우 효율적입니다.

공간 복잡도

DP 배열을 사용하기 때문에 공간 복잡도는 O(m * n)입니다. 하지만, 이전 행의 결과만 필요하기 때문에 공간을 최적화 할 수 있습니다.

최적화 방법

DP 배열 대신 한 행의 결과만 저장하여 공간 복잡도를 O(n)으로 줄일 수 있습니다. 다음은 이러한 최적화를 적용한 코드입니다:

public class OptimizedLargestSquare {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;

        int maxSide = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int prev = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j]; // 현재 DP[j] 값을 저장
                if (matrix[i][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    dp[j] = 0; // 1이 아닌 경우
                }
                prev = temp; // 이전 DP[j] 값을 저장
            }
        }

        return maxSide * maxSide;
    }
}

    

마무리

가장 큰 정사각형 찾기 문제는 동적 프로그래밍의 중요성을 잘 보여주는 문제입니다. 이 문제를 통해 알고리즘 문제 해결 능력을 키우고, 코딩 테스트에서 자주 출제되는 패턴을 연습할 수 있습니다.