두 개의 긴 문자열 데이터가 주어졌을 때, 두 문자열이 얼마나 비슷한지(유사도) 판별하는 것은 현대 컴퓨터 과학에서 대단히 중요한 기술입니다. 염기서열(DNA)이 얼마나 일치하는지 분석하는 바이오 인포매틱스(Bioinformatics), 두 소스 코드 파일의 변경 사항을 비교하여 보여주는 깃(Git)의 diff 기능, 맞춤법 검사기와 검색어 자동교정 시스템 등 수많은 첨단 기술의 핵심 엔진으로 자리 잡고 있는 것이 바로 '최장 공통 부분 수열(Longest Common Subsequence, 이하 LCS)' 알고리즘입니다. 코딩 테스트에서는 단순히 "LCS의 길이가 얼마인가?"를 묻는 것을 넘어, "길이를 구했다면, 그 실제 문자열이 무엇인지 과정까지 역추적하여 출력하라"는 극악의 난이도를 자랑하는 심화 문제로 진화했습니다. 2차원 DP 테이블을 거꾸로 훑어 올라가며 정답의 발자취를 찾아내는 역추적(Backtracking) 기법의 마법을 낱낱이 파헤쳐 봅니다.
1. 부분 문자열(Substring) vs 부분 수열(Subsequence)의 차이점
LCS를 완벽히 이해하기 위해서는 가장 먼저 두 단어의 결정적인 차이를 짚고 넘어가야 합니다. 문자열 "ABCDEF"가 있을 때:
- 부분 문자열(Substring): 글자들이 반드시 연속적으로 빈틈없이 붙어 있어야 합니다.
"BCD"는 맞지만,"ACF"는 틀립니다. - 부분 수열(Subsequence): 글자들이 연속해서 붙어있지 않고 듬성듬성 떨어져 있어도, 오른쪽으로 향하는 순서(방향성)만 맞으면 인정됩니다. 즉
"A"를 뽑고, 중간 글자를 건너뛰어"C"와"F"를 뽑은"ACF"도 올바른 부분 수열로 인정받습니다. 우리가 배우는 LCS 알고리즘은 바로 이 '건너뛰기'를 허용하는 유연한 방식입니다.
2. 2차원 DP 테이블 설계와 마법의 점화식
문자열 A(길이 N)와 문자열 B(길이 M)의 LCS를 구하기 위해, 우리는 dp[i][j]라는 거대한 2차원 배열을 도화지처럼 펼칩니다. 이 배열이 의미하는 바는 "문자열 A를 i번째 글자까지 자르고, 문자열 B를 j번째 글자까지 잘랐을 때, 두 조각이 공유하는 최대 LCS의 길이"입니다.
2-1. 점화식의 2가지 분기점 (같을 때 vs 다를 때)
문자열을 한 글자씩 늘려가며 대조할 때, 우리는 오직 맨 끝에 추가된 두 글자만 쳐다보고 다음 두 가지 행동 중 하나를 취합니다.
- 두 글자가 서로 같을 때 (Match):
A[i] == B[j]
기적처럼 두 글자가 맞았습니다! 이 글자는 무조건 공통 수열에 편입시켜야 합니다. 따라서 두 글자가 모두 추가되기 직전의 최고 기록(대각선 왼쪽 위)에 1을 더해줍니다.dp[i][j] = dp[i-1][j-1] + 1 - 두 글자가 서로 다를 때 (Mismatch):
A[i] != B[j]
둘 중 최소한 하나는 쓸모없는 잉여 글자입니다. A의 마지막 글자를 버리거나, B의 마지막 글자를 버려보는 두 가지 과거 시나리오 중, LCS 길이가 더 길었던 (더 이득이었던) 쪽의 기록을 그대로 복사해서 가져옵니다.dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
이 점화식을 2중 for문으로 돌리면 배열의 우측 하단 끝자락인 dp[N][M]에 최종 LCS의 최대 길이가 기록됩니다.
3. 진짜 LCS 문자열을 찾는 역추적(Backtracking) 알고리즘
길이를 구하는 것은 쉬우나, 실제 어떤 알파벳들이 모여서 সেই 길이를 만들었는지 추출하려면 완성된 2차원 DP 테이블의 우측 하단 끝점 dp[N][M]에서부터 출발하여 배열을 거꾸로 거슬러 올라가는 험난한 역추적 여행을 시작해야 합니다.
3-1. 테이블을 거슬러 올라가는 3가지 등산 규칙
현재 내 위치를 (i, j)라고 할 때, 다음 조건에 따라 이동하며 문자열을 수집합니다.
- 왼쪽 값
dp[i][j-1]과 내 값이 같은가?
같다면, 내 위치의 글자는 LCS에 기여하지 못한 잉여 글자입니다. 가차 없이 왼쪽 칸으로 이동합니다.j-- - 위쪽 값
dp[i-1][j]와 내 값이 같은가?
마찬가지로 잉여 글자입니다. 가차 없이 위쪽 칸으로 이동합니다.i-- - 왼쪽도 다르고, 위쪽도 다른가? (핵심 도약점)
드디어 찾았습니다! 이 칸은 위나 왼쪽에서 복사해 온 값이 아니라, 두 글자가 일치하여 대각선 위dp[i-1][j-1]에서 1을 더해 내려온 영광의 흔적입니다. 이 순간의 문자A[i](혹은B[j])를 정답 배열에 저장하고, 곧바로 대각선 왼쪽 위로 점프하여 올라갑니다.i--; j--;
i나 j가 0이 될 때까지 이 등산을 반복한 뒤, 수집된 문자들을 반대로 뒤집어주면(Reverse) 마침내 우리가 그토록 찾던 진짜 완벽한 최장 공통 부분 수열(LCS) 문자열이 모습을 드러냅니다.
1. 최장 공통 부분 수열(LCS)은 두 문자열이 끊어져 있더라도 순서를 유지하며 공유하는 가장 긴 수열을 찾는 핵심 알고리즘으로, DNA 분석이나 Git diff 엔진에 사용됩니다.
2. 두 문자가 같으면 대각선 위 값 + 1을 하고, 다르면 위쪽과 왼쪽 값 중 큰 값을 그대로 끌고 오는 2차원 점화식(DP)을 통해 길이를 구합니다.
3. 실제 문자열을 알아내려면 완성된 DP 테이블의 우측 하단 끝에서부터 시작하여, 왼쪽/위쪽 값과 다를 때 해당 문자를 저장하고 대각선으로 점프하는 역추적(Backtracking) 기법을 수행해야 합니다.