문제 설명
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)을 이용하여 해결할 수 있습니다. 동적 프로그래밍의 기본 아이디어는 이전에 계산된 결과를 사용하여 새로운 결과를 효율적으로 계산하는 것입니다. 다음과 같이 진행됩니다:
- 새로운 2차원 DP 배열을 생성합니다. DP[i][j]는 (i, j) 위치에서 정사각형의 최대 변의 길이를 나타냅니다.
- 배열의 요소를 순회하며, 만약 matrix[i][j]가 1이라면, DP[i][j]는 다음의 수식을 따릅니다:
- 단, i와 j가 0일 때는 DP[i][j]는 matrix[i][j]의 값과 같아야 합니다.
- 최대 변의 길이를 기억하고, 이를 통해 최대 넓이를 계산합니다.
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1
구현
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;
}
}
마무리
가장 큰 정사각형 찾기 문제는 동적 프로그래밍의 중요성을 잘 보여주는 문제입니다. 이 문제를 통해 알고리즘 문제 해결 능력을 키우고, 코딩 테스트에서 자주 출제되는 패턴을 연습할 수 있습니다.
팁: 이 문제는 자주 출제되는 주제이므로 여러 차원에서 접근해 보시는 것을 추천드립니다. 기초부터 차근차근 연습하시기 바랍니다.