최장 공통 부분 수열(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))

알고리즘

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

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

DP 테이블 생성 예시

1. 한 글자씩 차례로 비교를 한다. G-T, G-T, G-C, G-A, G-C, G-G, G-C, G-A를 비교하고 그 다음 A-T, A-T, A-C, A-A, A-C, ... ,를 비교한다.
2. 비교하다 서로 다른 문자가 나오면 한칸 위, 또는 한칸 왼쪽의 숫자 중 큰 숫자를 적는다.
3. 비교하다 서로 같은 문자가 나오면 한칸 위 + 한칸 왼쪽 위, 즉 대각선 위의 숫자에 +1을 한 숫자를 적는다.
4. 아래 예시의 경우 G와 G가 같기 때문에 그 대각선 위치의 0에서 1을 더한 값을 적는 것이다. 그리고 같은 줄 오른쪽이나 아래쪽은 2번의 규칙에 따라서 1이 죽 이어지게 된다.
5. 두번쨰 줄에 A와 A가 처음 만났을 때는 대각선 위가 0이므로 여전히 1을 적는다. 그리고 2번의 규칙에 따라 계속 1이 이어지다가, 마지막에 A를 한번 더 만났을 때는 대각선 위의 숫자가 1이므로 2를 적게 된다.
6. 이렇게 끝까지 수행을 하고 나면 DP 테이블이 완성된다.

백테스팅 과정 예시

백트래킹 과정에서는 현재 셀 (i, j)에서 다음의 규칙을 따릅니다:

1. 문자가 같은 경우
   • 만약 X[i-1] == Y[j-1]라면, 이 문자는 LCS의 일부이다.
   • 그러므로 해당 문자를 LCS에 추가하고, 대각선 왼쪽 위 (i-1, j-1)로 이동합니다.
   • 이 과정은 “현재 문자를 LCS에 포함시켰으니, 이전 부분 문제로 넘어가자”는 의미이다.
2. 문자가 다른 경우
   • 만약 X[i-1]와 Y[j-1]이 다르다면,
   • 위쪽 셀 (i-1, j)와 왼쪽 셀 (i, j-1) 중 더 큰 값(혹은 같은 값인 경우 둘 다)을 가진 방향으로 이동합니다.
   • 여기서 둘 다 같은 경우는 모든 경로를 고려해야 한다는 의미이다. (모든 가능한 LCS를 구하기 위해 분기함)
3. 종료 조건
   1. i == 0 또는 j == 0이 되면, 더 이상 비교할 문자가 없으므로 역추적을 종료한다.

이런 경로를 따르기 때문에 백트레킹은 여러 경로로 분기가 되고, 여러 LCS를 구하는 과정이 된다.

경로 1

CCGA는 하나의 LCS라는 결론이 났다.

경로 2

ACCA도 하나의 LCS라는 결론이 난다.

이렇게 양쪽 방향으로 갈 수 있는 경우를 다 분기해서 가다 보면 모든 경로를 추적하여 모든 LCS를 구할 수 있다. 전체 답이 궁금하면 아래 파이썬 코드를 실행시켜 볼 수 있다.

예제 코드

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

from functools import lru_cache

def build_lcs_table(X, Y):
    """X와 Y로부터 LCS 테이블(dp)를 생성"""
    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])
    return dp


def backtrack_all_lcs(X, Y, dp):
    """dp 테이블 기반으로 모든 LCS 문자열을 재귀적으로 역추적"""
    m, n = len(X), len(Y)
    
    @lru_cache(maxsize=None)
    def backtrack(i, j):
        if i == 0 or j == 0:
            return set([""])
        if X[i - 1] == Y[j - 1]:
            prev = backtrack(i - 1, j - 1)
            # p + X[i-1]는 올바른 순서의 문자열을 만듦
            return set([p + X[i - 1] for p in prev])
        else:
            results = set()
            if dp[i - 1][j] >= dp[i][j - 1]:
                results.update(backtrack(i - 1, j))
            if dp[i][j - 1] >= dp[i - 1][j]:
                results.update(backtrack(i, j - 1))
            return results

    # raw_lcs_set는 올바른 순서의 문자열들을 포함하고 있으므로,
    # 여기서 뒤집을 필요가 없다!
    return backtrack(m, n)


def lcs_all(X, Y):
    """입력 문자열 X, Y에 대해 LCS 길이와 모든 공통 수열을 반환"""
    dp = build_lcs_table(X, Y)
    all_lcs = backtrack_all_lcs(X, Y, dp)
    return dp[len(X)][len(Y)], all_lcs


# 예제 실행
if __name__ == "__main__":
    X = "GACTCGAA"
    Y = "TTCACGCA"
    length, sequences = lcs_all(X, Y)
    print("LCS 길이:", length)
    print("모든 LCS 수열:")
    for s in sorted(sequences):
        print(s)

시간 복잡도

이 알고리즘의 시간 복잡도는 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.