최장 공통 부분 수열 편집하기

최장 공통 부분 수열(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을 사용하여 최장 공통 부분 수열을 구하는 코드이다.<syntaxhighlight lang="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)
</syntaxhighlight>
==시간 복잡도==
이 알고리즘의 시간 복잡도는 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.
[[분류:알고리즘]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*