최장 공통 부분 수열 (LCS) 문제를 다이나믹 프로그래밍으로 풀기

문제 정의

최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제는 두 문자열의 부분 수열 중 가장 긴 공통 부분 수열을 찾는 것입니다. 예를 들어, 문자열 ABCBDAB와 BDCAB가 주어졌을 때, 이 두 문자열의 LCS는 BCAB로 길이는 4입니다. 이 문제는 문자열 비교와 관련된 여러 응용 분야에서 매우 중요하게 쓰입니다.

다이나믹 프로그래밍 접근법

LCS 문제를 단순히 브루트 포스로 해결하려면 모든 부분 수열을 생성하고 비교해야 하므로 매우 비효율적입니다. 하지만 다이나믹 프로그래밍을 이용하면 효율적으로 문제를 해결할 수 있습니다. 다이나믹 프로그래밍의 핵심은 문제를 더 작은 부분 문제로 나누고, 부분 문제의 해답을 재사용하는 것입니다.

알고리즘 개요

다이나믹 프로그래밍을 사용하여 LCS 문제를 해결하는 방식은 다음과 같은 테이블 dp를 작성하는 것입니다. 이 테이블 dp[i][j]는 첫 번째 문자열의 앞 부분 X[0...i-1]과 두 번째 문자열의 앞 부분 Y[0...j-1]의 LCS 길이를 저장합니다.

초기화

• dp[0][j] 및 dp[i][0]은 0으로 초기화합니다. 이는 한 문자열이 비어있다면 LCS의 길이가 0이라는 것을 의미합니다.

상태 전이

• 문자가 일치하는 경우: X[i-1] == Y[j-1]이라면, dp[i][j] = dp[i-1][j-1] + 1입니다. 이는 현재 문자가 일치하면 이전 부분 수열의 LCS 길이에 1을 더하는 것입니다.
• 문자가 일치하지 않는 경우: X[i-1] != Y[j-1]이라면, dp[i][j] = max(dp[i-1][j], dp[i][j-1])입니다. 이는 마지막 문자가 다르면, 이전 단계에서 최댓값을 가져오는 것입니다.

예시 코드

다음은 파이썬을 이용한 LCS 문제 해결의 예시 코드입니다.

python
def lcs(X, Y):
    m = len(X)
    b = len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # dp 테이블 작성
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # LCS 길이
    return dp[m][n]

# 예시 사용
X = 'ABCBDAB'
Y = 'BDCAB'
print('LCS 길이: ', lcs(X, Y))

이 코드는 dp 테이블을 사용하여 LCS 길이를 계산합니다. dp 테이블을 작성하는 데 O(mn)의 시간 복잡도가 소요되며, 공간 복잡도 또한 O(mn)입니다.

테이블 재구성으로 LCS 자체 찾기

LCS의 길이뿐만 아니라 실제 공통 부분 수열을 찾고자 한다면, dp 테이블을 역추적하면 됩니다. 이를 위해 LCS를 구성하는 캐릭터를 추적하여 최종 LCS 문자열을 구성합니다. 다음은 이를 구현한 코드입니다.

python
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # dp 테이블 작성
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # LCS 길이
    lcs_length = dp[m][n]

    # LCS 문자열 구성
    lcs_str = [''] * lcs_length    # LCS 문자열 배열
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_str[lcs_length - 1] = X[i - 1]
            i -= 1
            j -= 1
            lcs_length -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(lcs_str)

# 예시 사용
X = 'ABCBDAB'
Y = 'BDCAB'
print('LCS: ', lcs(X, Y))

위의 코드는 dp 테이블 작성 후, 공통 부분 수열을 역추적하여 최종 LCS 문자열을 반환합니다. 이로 인해 최종 결과를 쉽게 확인할 수 있습니다.

결론

다이나믹 프로그래밍을 통한 LCS 문제 해결은 효율적인 방법이며, 문자열 비교 문제를 해결하는 데 매우 유용합니다. 이 방법을 이해하고 활용하면, 더 복잡한 문제에도 다이나믹 프로그래밍을 적용할 수 있는 기초를 다질 수 있습니다. 앞으로도 다양한 알고리즘 문제에 이 개념을 적용해 보시기 바랍니다.