IT용어위키

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

개요

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

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

정의

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

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

점화식

기본 아이디어

기저 사례(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))

알고리즘

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

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

예제 코드

다음은 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)

시간 복잡도

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

활용

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

같이 보기

참고 문헌

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.