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

안녕하세요, 코틀린을 활용한 코딩테스트 문제 풀이 강좌에 오신 것을 환영합니다. 이번 시간에는 “가장 큰 정사각형 찾기”라는 문제를 해결해보겠습니다. 이 문제는 주어진 2차원 배열에서 가장 큰 정사각형의 넓이를 찾는 과제입니다. 이 문제를 통해 동적 프로그래밍(Dynamic Programming)의 기초 개념을 익히고, 코틀린 언어의 문법과 특징도 이해할 수 있습니다.

문제 설명

주어진 m x n 크기의 2차원 이진 배열이 있습니다. 이 배열에서 ‘1’은 해당 위치에서 정사각형이 형성될 수 있음을 의미하고, ‘0’은 그렇지 않음을 의미합니다. 가장 큰 정사각형의 넓이를 찾는 것이 목표입니다.

예를 들어, 다음과 같은 배열이 있을 때:

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

이 경우, 가장 큰 정사각형의 넓이는 4입니다. (2×2 정사각형)

문제 접근 방법

이 문제를 해결하기 위해 우리는 동적 프로그래밍을 사용할 것입니다. 다음은 문제를 해결하기 위한 주요 단계입니다:

  1. DP 배열 초기화: 입력받은 2차원 배열과 같은 크기를 가지는 DP 배열을 생성합니다. 이 DP 배열의 각 원소는 (i, j) 위치에서 끝나는 정사각형의 한 변의 길이를 나타냅니다.
  2. 상태 전이 관계 설정: 만약 grid[i][j]가 ‘1’이라면, DP[i][j]는 DP[i-1][j], DP[i][j-1], DP[i-1][j-1] 중 최소값 + 1이 됩니다. 이는 (i,j)에서의 가장 큰 정사각형의 변 길이를 결정합니다.
  3. 최대 정사각형 변 길이 추적: 이 과정을 통해 가장 큰 정사각형의 변 길이를 추적하고, 마지막에 그 값을 제곱하여 넓이를 계산합니다.

코드 구현

이제 위의 알고리즘을 코틀린으로 구현해보겠습니다. 아래는 해당 알고리즘의 코드입니다:


    fun maximalSquare(matrix: Array): Int {
        if (matrix.isEmpty()) return 0

        val m = matrix.size
        val n = matrix[0].size
        val dp = Array(m) { IntArray(n) }
        var maxSide = 0

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1 // 첫 행이나 첫 열의 경우
                    } else {
                        dp[i][j] = minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    }
                    maxSide = maxOf(maxSide, dp[i][j])
                }
            }
        }
        return maxSide * maxSide // 정사각형의 넓이 반환
    }

코드 설명

코드는 2차원 배열을 입력으로 받아, 각 셀에 대해 해당 위치에서 끝나는 정사각형의 한 변의 길이를 계산합니다. 다음은 코드의 주요 부분에 대한 설명입니다:

  • 초기 검증: 입력된 행렬이 비어있는지 검사합니다. 비어있다면 0을 반환합니다.
  • 이중 루프: 각 원소를 순회하며, ‘1’일 경우 DP 테이블에 값을 업데이트합니다.
  • 최대 사이드 업데이트: 각 경우 최댓값을 추적하여, 마지막에 이를 제곱하여 결과를 반환합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(m * n)이며, DP 배열을 사용하므로 공간 복잡도 또한 O(m * n)입니다. 하지만 공간을 최적화할 수도 있습니다. DP 배열 대신 두 개의 변수를 사용하여 현재 행과 이전 행의 정보를 저장함으로써 공간 복잡도를 O(n)으로 줄일 수 있습니다.

선택적 공간 최적화 코드


    fun maximalSquare(matrix: Array): Int {
        if (matrix.isEmpty()) return 0
        val m = matrix.size
        val n = matrix[0].size
        val dp = IntArray(n)
        var maxSide = 0
        var prev = 0

        for (i in 0 until m) {
            for (j in 0 until n) {
                val temp = dp[j]
                if (matrix[i][j] == '1') {
                    dp[j] = if (i == 0 || j == 0) 1 else minOf(dp[j], dp[j - 1], prev) + 1
                    maxSide = maxOf(maxSide, dp[j])
                } else {
                    dp[j] = 0
                }
                prev = temp
            }
        }
        return maxSide * maxSide
    }

결론

이번 강좌를 통해 “가장 큰 정사각형 찾기” 문제를 해결하는 방법을 학습했습니다. 이 과정에서 동적 프로그래밍의 기본적인 개념을 이해하고, 코틀린 언어로 알고리즘을 구현하는 방법을 배웠습니다. 이러한 알고리즘 문제를 통해 문제 해결 능력을 향상시키고, 코딩 테스트 준비에 큰 도움이 될 것입니다. 다음 시간에는 또 다른 흥미로운 알고리즘 문제를 다뤄보겠습니다. 감사합니다!