최장 공통 부분수열(LCS) 계산기

최장 공통 부분 수열 계산기 쉽게 이해하기 — 개념과 원리

부분 수열은 원래 순서를 지키되 중간 글자를 건너뛸 수 있는 수열로, "ACE"는 "ABCDE"의 부분 수열입니다. 두 문자열의 최장 공통 부분 수열(LCS)은 두 문자열 모두에 같은 순서로 나타나는 가장 긴 수열입니다. diff 같은 파일 비교 도구, 버전 관리의 병합, 표절 검사, DNA 서열 정렬의 바탕이 되는 개념입니다. 이 계산기는 LCS의 길이와 LCS 하나를 보여 줍니다.

계산 방법

L[i][j]를 A의 앞 i글자와 B의 앞 j글자의 LCS 길이라고 합니다.

• L[i][0] = L[0][j] = 0입니다.
• A의 i번째 글자와 B의 j번째 글자가 같으면 L[i][j] = L[i−1][j−1] + 1입니다.
• 다르면 L[i][j] = max(L[i−1][j], L[i][j−1])입니다.

답은 L[m][n]입니다. LCS 하나를 복원할 때는 표의 오른쪽 아래에서 거꾸로 따라가며, 글자가 같으면 그 글자를 취하고 다르면 더 큰 쪽으로 이동합니다(같으면 위쪽). 표 계산에 O(mn)의 시간과 메모리가 들기 때문에 두 길이의 곱이 4,000,000을 넘으면 계산하지 않습니다.

원리

마지막 글자를 보면 됩니다. 두 글자가 같으면 최적의 LCS가 항상 그 글자로 끝나도록 만들 수 있으므로, 문제는 두 문자열 모두 한 글자씩 짧아진 경우로 줄어듭니다. 다르면 둘 중 적어도 하나는 LCS에 들어가지 않으므로 A의 마지막 글자를 뺀 경우와 B의 마지막 글자를 뺀 경우 중 더 나은 쪽이 답입니다. 모든 부분 문제는 앞부분끼리의 쌍이고 그 수가 (m + 1)(n + 1)개뿐이라 동적 계획법으로 효율적으로 풀립니다.

예제 풀이

1. 입력값: A = "ABCBDAB"(7글자), B = "BDCABA"(6글자)입니다.
2. 8 × 7 표를 채우면 L[7][6] = 4입니다.
3. 거꾸로 따라가면 BCBA를 얻습니다. A에서는 2, 3, 4, 6번째, B에서는 1, 3, 5, 6번째 글자입니다.
4. BDAB, BCAB처럼 길이 4인 다른 LCS도 있으며, 계산기는 그중 하나를 보여 줍니다.

결과 해석

LCS 길이를 긴 문자열의 길이로 나누면 대략적인 겹침 비율이 됩니다(4 ÷ 7 ≈ 57%). 삽입과 삭제만 허용하는 편집 거리는 m + n − 2 · LCS로, 이 예에서는 7 + 6 − 8 = 5입니다. diff 도구도 같은 관점으로 LCS에 없는 줄을 삭제되거나 추가된 줄로 표시합니다.

흔한 실수

• 부분 수열과 부분 문자열을 혼동합니다. 부분 문자열은 연속해야 하므로 별개의 문제입니다.
• 답이 하나뿐이라고 생각합니다. 길이가 같은 LCS가 여러 개인 경우가 흔합니다.
• 대소문자와 공백도 글자로 센다는 점을 잊습니다.

자주 묻는 질문

LCS의 시간 복잡도는 얼마인가요?

표준 방법으로 O(mn)이며, 10,000글자짜리 두 문자열이면 1억 칸입니다.

모든 LCS를 구할 수 있나요?

거꾸로 따라갈 때 값이 같은 갈림길마다 나누어 가면 되지만, 개수가 매우 빠르게 늘 수 있습니다.

diff는 LCS를 어떻게 쓰나요?

각 줄을 하나의 기호로 보고 공통 줄은 남기며, 나머지 줄을 삭제 또는 추가로 표시합니다.

출처: T. H. Cormen 외, Introduction to Algorithms, MIT Press · D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences", Communications of the ACM 18(6), 1975