최장 공통 부분 수열

최장 공통 부분 수열(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를 구할 수 있다.

4.1 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 테이블이 완성된다.

		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

4.2 백테스팅 과정 예시

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

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를 구할 수 있다. 전체 답이 궁금하면 아래 파이썬 코드를 실행시켜 볼 수 있다.

5 예제 코드

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

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.