최장 공통 부분 수열

최장 공통 부분 수열(Longest Common Subsequence, LCS)은 두 개의 문자열에서 순서를 유지하면서 나타나는 가장 긴 부분 수열을 찾는 문제로, 동적 계획법을 사용하여 해결된다.

1 개요

최장 공통 부분 수열은 여러 문자열 비교 문제에서 중요한 개념으로 활용된다. 이는 반드시 연속된 문자가 아니어도 되며, 순서만 유지되면 된다.

예를 들어, 문자열 "ACDBE"와 "ABCDE"의 최장 공통 부분 수열은 "ACDE"이다.

2 정의

두 문자열 X와 Y가 주어졌을 때, 최장 공통 부분 수열 LCS(X, Y)는 다음 성질을 만족한다.

• LCS(X, Y)는 X와 Y의 부분 수열이다.
• LCS(X, Y)의 길이는 가능한 최장 길이여야 한다.

3 점화식

기본 아이디어

• 기저 사례(Base Case)
  • 하나의 문자열이 비어 있으면 공통 부분 수열이 없으므로 LCS 길이는 0.
• 두 문자열의 마지막 문자가 같다면
  • LCS(X[:-1], Y[:-1]) + 1 (즉, 두 문자열에서 각각 마지막 문자를 제거하고 나머지 문자열의 LCS를 구한 후 1을 더함).
• 두 문자열의 마지막 문자가 다르면
  • 마지막 문자를 제거한 두 가지 경우 중 더 긴 LCS를 선택.
  • LCS(X[:-1], Y) (X의 마지막 문자 제외)
  • LCS(X, Y[:-1]) (Y의 마지막 문자 제외)
    • 이 둘 중 더 긴 값을 선택하면 최적의 해를 보장할 수 있음.

동적 계획법을 이용하여 최장 공통 부분 수열을 계산하는 점화식은 다음과 같다.

• X[i] == Y[j]이면
  • LCS(i, j) = LCS(i-1, j-1) + 1
• X[i] ≠ Y[j]이면
  • LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

4 알고리즘

동적 계획법을 이용한 최장 공통 부분 수열 알고리즘은 다음과 같은 방식으로 수행된다.

1. 두 문자열 X와 Y의 길이를 기반으로 2차원 DP 테이블을 생성한다.
2. 점화식을 이용하여 테이블을 채운다.
3. 최종적으로 LCS의 길이를 얻고, 역추적하여 실제 LCS를 구할 수 있다.

5 예제 코드

다음은 Python을 사용하여 최장 공통 부분 수열을 구하는 코드이다.

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

    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_str = ""
    i, j = m, n
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lcs_str = X[i - 1] + lcs_str
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return dp[m][n], lcs_str

# 예제 실행
X = "ACDBE"
Y = "ABCDE"
length, sequence = lcs(X, Y)
print("LCS 길이:", length)
print("LCS 문자열:", sequence)

6 시간 복잡도

이 알고리즘의 시간 복잡도는 O(mn)이며, m과 n은 두 문자열의 길이이다. 공간 복잡도는 O(mn)이지만, 최적화하면 O(min(m, n))까지 줄일 수 있다.

7 활용

• DNA 서열 분석 - 유전자 서열 비교
• 문서 비교 - 텍스트 유사도 분석
• 파일 비교 도구 - diff 알고리즘에 사용
• 버전 관리 시스템 - Git, SVN 등에서 변경 사항 추적

8 같이 보기

• 동적 계획법
• 편집 거리
• 최장 증가 부분 수열
• 서열 정렬 알고리즘

9 참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
• Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press.