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

1. 문제 설명

이 문제는 주어진 이진 행렬(matrix) 내에서 가장 큰 크기의 단일 정사각형을 찾아 그 크기를 반환하는 문제입니다.
이진 행렬은 각각의 요소가 0 또는 1로 구성되어 있습니다.
1로 구성된 정사각형의 가장 큰 크기를 찾아야 하며, 크기는 정사각형의 변의 길이로 정의됩니다.

예시

  • 입력: matrix = [[0,1,1,1,0],[0,1,1,1,1],[0,1,1,1,1],[0,0,0,0,0]]
  • 출력: 3 (가장 큰 정사각형의 변의 길이)

2. 문제 해결 접근법

이 문제를 해결하기 위해서는 동적 프로그래밍(Dynamic Programming) 기법을 사용할 수 있습니다.
기본 아이디어는 각 위치에서 그 위치를 기준으로 왼쪽, 위, 대각선 위 위치의 정보(최소 크기)를 이용하여
현재의 위치에서 만들 수 있는 정사각형의 크기를 결정하는 것입니다.

2.1 상태 정의

dp[i][j]를 i행 j열에서 만들 수 있는 정사각형의 최대 크기로 정의합니다.
즉, dp[i][j] 값은 matrix[i][j]가 1일 경우,
dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최소값에 1을 더한 값으로 설정합니다.
만약 matrix[i][j]가 0이라면, dp[i][j]는 0이 됩니다.

2.2 점화식

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 (단, matrix[i][j] == 1일 경우)

2.3 초기 조건

첫 번째 행과 첫 번째 열의 경우, matrix[i][j] 값이 1이면 dp[i][j]도 1,
0이면 0으로 초기화합니다.

3. 알고리즘 구현

다음은 위의 접근법을 기반으로 한 C# 코드입니다. 

C#
public class Solution {
    public int MaximalSquare(char[][] matrix) {
        if (matrix.Length == 0) return 0;
        
        int maxSide = 0;
        int rows = matrix.Length;
        int cols = matrix[0].Length;
        int[][] dp = new int[rows][];
        
        for (int i = 0; i < rows; i++) {
            dp[i] = new int[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; // 가장자리의 경우 직접 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; // 정사각형의 넓이를 반환
    }
}

4. 복잡도 분석

이 알고리즘의 시간복잡도는 O(m * n)입니다. 여기서 m은 행렬의 행 수, n은 열 수입니다.
각 요소를 한 번씩만 확인하기 때문에 이와 같은 복잡도가 나타납니다.
공간복잡도 또한 동적 배열을 이용하기 때문에 O(m * n)으로 동일합니다.

5. 결론

이 문제는 동적 프로그래밍의 강력한 활용 예를 보여줍니다.
이진 행렬에서 정사각형을 찾는 이 문제를 통하여, 동적 프로그래밍의 사고방식과 알고리즘을 올바르게 설계하는 방법을 배울 수 있었습니다.
C#에서 이러한 문제를 해결하는 방식에 대해 충분한 이해를 돕는 것이 중요합니다.

6. 추가적인 학습 자료