코틀린 코딩테스트 강좌, 최장 공통 부분 수열 찾기

1. 서론

알고리즘 문제 해결의 핵심은 다양한 문제를 이해하고 해결하는 능력을 기르는 것입니다. 그 중에서도 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제는 여러 알고리즘 시험에서 자주 등장하는 기본적인 문제입니다. 이 글에서는 코틀린을 이용하여 LCS 문제를 해결하는 과정을 자세히 살펴보겠습니다.

2. 문제 설명

주어진 두 문자열이 있을 때, 이들 문자열에서 각각의 문자를 삭제하지 않고 공통으로 나타나는 가장 긴 부분 수열의 길이를 구하는 문제입니다. 다시 말해, 두 문자열에서 문자의 순서를 유지하면서 공통으로 찾아낼 수 있는 가장 긴 서브 시퀀스를 찾는 것이죠.

예제

문자열1: “ABCBDAB”
문자열2: “BDCAB”
최장 공통 부분 수열: “BCAB” (길이: 4)

3. 문제 해결의 접근법

LCS 문제를 해결하기 위한 일반적인 접근법은 동적 프로그래밍(Dynamic Programming)입니다. 동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법론입니다. 여기에선 두 문자열의 각 문자를 비교하며, 최대 길이를 계산해 나갑니다.

3.1. 동적 프로그래밍 테이블 정의

먼저, 두 문자열의 길이를 각각 m, n이라고 할 때, dp[i][j]를 문자열1의 처음 i글자와 문자열2의 처음 j글자까지의 LCS의 길이로 정의합니다. 이 테이블의 크기는 (m+1) x (n+1)입니다. 테이블의 첫 번째 행과 열은 0으로 초기화합니다.

3.2. 점화식 설정

두 문자열의 마지막 문자까지 비교하며 다음의 규칙으로 테이블을 채워 나갑니다:

문자가 같을 경우: dp[i][j] = dp[i-1][j-1] + 1
문자가 다를 경우: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3.3. 결과 추출

이 과정을 통해 완성된 dp 테이블의 마지막 셀 dp[m][n]에는 두 문자열의 LCS 길이가 저장됩니다.

4. 코틀린 구현

이제 이론적인 설명을 바탕으로 코틀린을 이용해 실제로 LCS를 계산해보겠습니다.


fun longestCommonSubsequence(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    for (i in 1..m) {
        for (j in 1..n) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[m][n]
}

fun main() {
    val s1 = "ABCBDAB"
    val s2 = "BDCAB"
    println("최장 공통 부분 수열의 길이: ${longestCommonSubsequence(s1, s2)}")
}

5. 분석

위의 코드는 O(m * n)의 시간 복잡도와 O(m * n)의 공간 복잡도를 가집니다. 따라서 문자열의 길이가 길어질수록 성능이 감소할 수 있습니다. 그러나 LCS 문제는 다양한 최적화 기법을 통해 개선될 수 있습니다.

5.1. 공간 효율성 개선

현재는 2D 배열을 사용했지만, 실제로는 이전 행의 값만 필요하므로 1D 배열로도 해결 가능합니다. 이를 통해 공간 복잡도를 O(n)으로 줄일 수 있습니다.


fun longestCommonSubsequenceOptimized(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dp = IntArray(n + 1)

    for (i in 1..m) {
        val prev = IntArray(n + 1)
        for (j in 1..n) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[j] = prev[j - 1] + 1
            } else {
                dp[j] = maxOf(dp[j - 1], prev[j])
            }
            prev[j] = dp[j]
        }
    }
    return dp[n]
}

6. 결론

최장 공통 부분 수열 문제는 알고리즘 공부와 코드 테스트에서 매우 중요한 문제입니다. 동적 프로그래밍을 활용하여 문제를 효율적으로 해결할 수 있으며, 여러 최적화 기법이 있음을 알게 되었습니다. 이 문제를 통해 알고리즘적 사고를 발전시키고 코틀린 프로그래밍을 연습할 수 있는 기회가 되길 바랍니다.