최장 공통 부분 수열

최장 공통 부분 수열(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 테이블 생성 예시

GACT CGAA와 TTCA CGCA를 비교해보자

1. 먼저 각 문자열을 축으로 한 매트리스를 그리고 0으로 초기화한다.
2. 한 글자씩 차례로 비교를 한다. 첫줄의 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, ... , A-A 를 비교한다.
3. 비교하다 서로 다른 문자가 나오면 한칸 위, 또는 한칸 왼쪽의 숫자 중 큰 숫자를 적는다.
4. 비교하다 서로 같은 문자가 나오면 한칸 위 + 한칸 왼쪽 위, 즉 대각선 위의 숫자에 +1을 한 숫자를 적는다.
   • 첫 번째 줄의 경우 윗 칸은 모두 0이므로, 우선 0으로 진행하다 같은 문자가 나오면 1을 적게 된다.
   • 1이 한번 나오면 같은 줄의 그 뒤는 최소 1로 계속 이어진다. 그리고 같은 문자가 한번 더 나오면 2가 되고, 2가 계속 이어진다.
   • 두 번째 줄부턴 왼쪽와 위쪽을 모두 봐야 한다. 겹치는 문자가 없어도 윗칸이 1이면 이 줄에서도 1을 가져간다.
     • 이미 이 줄에서 1이 나오고 있었는데 위에서 1을 만나더라도 그대로 1이다. 둘 중 큰 숫자를 가져가는 것이지 더해지는 것이 아니다.
5. 아래 예시의 경우 G와 G가 같기 때문에 그 대각선 위치의 0에서 1을 더한 값을 적는 것이다. 그리고 같은 줄 오른쪽이나 아래쪽은 2번의 규칙에 따라서 1이 죽 이어지게 된다.
6. 두번째 줄에 A와 A가 처음 만났을 때는 대각선 위가 0이므로 여전히 1을 적는다. 그리고 2번의 규칙에 따라 계속 1이 이어지다가, 마지막에 A를 한번 더 만났을 때는 대각선 위의 숫자가 1이므로 2를 적게 된다.
7. 이렇게 끝까지 수행을 하고 나면 DP 테이블이 완성된다.

		T	T	C	A	C	G	C	A
	0	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	1	1	1
A	0	0	0	0	1	1	1	1	2
C	0	0	0	1	1	2	2	2	2
T	0	1	1	1	1	2	2	2	2
C	0	1	1	2	2	2	2	3	3
G	0	1	1	2	2	2	3	3	3
A	0	1	1	2	3	3	3	3	4
A	0	1	1	2	3	3	3	3	4

백테스팅 과정 예시

백트래킹 과정에서는 현재 셀 (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

		T	T	C	A	C	G	C	A
	0	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	1	1	1
A	0	0	0	0	1	1	1	1	2
C	0	0	0	(1)	1	2	2	2	2
T	0	1	1	1	1	2	2	2	2
C	0	1	1	2	2	(2)	2	3	3
G	0	1	1	2	2	2	(3)	3	3
A	0	1	1	2	3	3	3	3	4
A	0	1	1	2	3	3	3	3	(4)

• A-A는 일치하므로 대각선 위로 이동한다.
• C-A는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 왼쪽을 선택한다.
• A-G는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 위쪽을 선택한다.
• G-G는 일치하므로 대각선 위로 이동한다.
• C-C도 일치하므로 대각선 위로 이동한다.
• A-T는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 왼쪽을 선택한다.
• C-T는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 위쪽을 선택한다.
• C-C는 일치하므로 대각선 위로 이동한다.
• 0이므로 종료한다.

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

경로 2

		T	T	C	A	C	G	C	A
	0	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	1	1	1
A	0	0	0	0	(1)	1	1	1	2
C	0	0	0	1	1	(2)	2	2	2
T	0	1	1	1	1	2	2	2	2
C	0	1	1	2	2	2	2	(3)	3
G	0	1	1	2	2	2	3	3	3
A	0	1	1	2	3	3	3	3	4
A	0	1	1	2	3	3	3	3	(4)

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.