LCS 알고리즘: 문자열 유사도 분석과 최장 공통 부분 수열
서로 다른 두 문장이나 유전자 서열이 얼마나 닮았는지 측정하는 기술은 현대 전산학에서 매우 중요한 위치를 차지합니다. 텍스트 에디터의 파일 비교(Diff), Git의 소스 코드 변경점 감지, 그리고 바이오인포매틱스의 DNA 서열 분석 등이 모두 하나의 뿌리에서 시작됩니다. 바로 최장 공통 부분 수열(Longest Common Subsequence, LCS)입니다. 본 포스팅에서는 LCS의 정의와 '최장 공통 부분 문자열'과의 차이점, 그리고 2차원 DP 테이블을 이용한 정교한 구현 원리를 상세히 파헤쳐 보겠습니다.
1. LCS의 정의와 Substring과의 결정적 차이
LCS를 공부할 때 가장 먼저 혼동하지 말아야 할 개념이 바로 부분 문자열(Substring)입니다. 부분 문자열은 '연속된' 공통 부분을 찾는 반면, 부분 수열(Subsequence)은 떨어져 있어도 순서만 유지된다면 공통 부분으로 인정합니다. 예를 들어 "ABCDE"와 "ACE"가 있을 때, 공통 부분 문자열은 "A" 혹은 "C" 혹은 "E"뿐이지만, 공통 부분 수열은 "ACE"가 됩니다. 이처럼 LCS는 데이터의 흐름 속에 숨겨진 전체적인 패턴의 일치성을 찾아내는 데 더 적합한 모델입니다.
2. 2차원 DP 테이블을 이용한 문제 해결 전략
두 문자열의 길이를 각각 $N, M$이라고 할 때, 우리는 $(N+1) \times (M+1)$ 크기의 2차원 배열 dp[i][j]를 생성합니다. 여기서 dp[i][j]는 "첫 번째 문자열의 i번째까지와 두 번째 문자열의 j번째까지의 LCS 길이"를 의미합니다. 테이블을 채워나가는 로직은 두 문자가 같은지 다른지에 따라 명확히 구분됩니다.
2-1. 점화식의 논리 구조
- 문자가 같은 경우:
str1[i] == str2[j]라면, 이 문자는 공통 수열에 포함될 수 있습니다. 따라서 대각선 왼쪽 위의 값에 1을 더합니다.dp[i][j] = dp[i-1][j-1] + 1 - 문자가 다른 경우: 이 문자는 현재 단계에서 공통 수열을 늘려주지 못합니다. 따라서 지금까지 구한 최선책 중 큰 값을 그대로 가져옵니다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
이 과정을 거치면 테이블의 가장 마지막 칸 dp[N][M]에 최장 공통 부분 수열의 길이가 저장됩니다. 이러한 접근은 복잡한 경우의 수를 체계적인 표 형태로 정리하여 누락 없이 정답을 도출하게 해줍니다.
3. 역추적(Backtracking)을 통한 실제 문자열 추출
길이뿐만 아니라 실제 공통 문자열이 무엇인지 알아야 할 때가 많습니다. 이때는 완성된 DP 테이블을 끝에서부터 역순으로 추적합니다. 현재 칸의 값이 왼쪽이나 위의 값과 같다면 그 방향으로 이동하고, 두 방향 모두 다르다면 그 지점이 바로 문자가 일치했던 지점이므로 결과 문자열에 추가하고 대각선 위로 이동합니다. 이 과정을 반복한 뒤 결과를 뒤집으면 실제 LCS를 얻을 수 있습니다.
4. 복잡도와 실무 활용의 무한한 가능성
LCS 알고리즘의 시간 및 공간 복잡도는 모두 $O(N \times M)$입니다. 문자열의 길이가 수천 자 수준이라면 매우 빠르게 동작합니다.
- 소스 코드 비교 도구: 두 파일 사이의 추가되거나 삭제된 라인을 감지할 때 사용됩니다.
- 생물 정보학: 두 종의 DNA 서열 유사도를 분석하여 진화론적 거리를 측정합니다.
- 표절 검사 시스템: 문서 간의 문장 구조가 얼마나 일치하는지 수치화하여 독창성을 평가합니다.
# 2차원 DP를 이용한 LCS 길이 계산 (Python)
def lcs(s1, s2):
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i-1] == s2[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[n][m]
1. 차이점: 연속되지 않아도 순서만 맞으면 공통 부분으로 인정하는 부분 수열을 찾습니다.
2. 핵심 로직: 2차원 DP 테이블을 사용하여 문자 일치 여부에 따라 값을 누적하거나 전이합니다.
3. 응용: 소스 코드 비교, 유전자 서열 분석 등 데이터 유사도 측정이 필요한 모든 곳에 쓰입니다.