최장 공통 부분 수열이란?
최장 공통 부분 수열(LCS, Longest Common Subsequence)은 두 수열에서 순서를 유지하되 꼭 연속일 필요는 없는 공통 부분 수열 중 가장 긴 것을 찾는 문제입니다. 예를 들어 ABCBDAB와 BDCAB의 LCS는 BCAB(길이 4)입니다.
부분 수열(subsequence)은 부분 문자열(substring)과 달리 연속이 아니어도 됩니다 — 사이를 건너뛰어도 순서만 지키면 됩니다. 파일 비교(diff), 생물정보학의 DNA 비교 등에 쓰입니다.
상태 정의
dp[i][j] = A의 앞 i글자와 B의 앞 j글자가 공유하는 LCS의 길이.
문자를 하나씩 늘려 가며 "두 끝 글자가 같은가?"만 보면 되도록 문제가 쪼개집니다.
점화식
A의 i번째 글자와 B의 j번째 글자를 비교합니다.
- •같다(A[i] == B[j]):
dp[i][j] = dp[i-1][j-1] + 1(공통 글자 하나 추가) - •다르다:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])(한쪽 글자를 버린 더 긴 쪽)
같으면 대각선 +1, 다르면 위·왼쪽 중 큰 값 — 이 한 줄이 핵심입니다.
동작 원리
1단계. 0번째 행과 열을 0으로 둡니다(빈 문자열과의 LCS는 0).
2단계. 표를 왼쪽 위에서 오른쪽 아래로 채웁니다. 각 칸은 위 점화식으로 결정됩니다.
3단계. dp[m][n]이 LCS의 길이입니다.
4단계(복원). 실제 수열이 필요하면 dp[m][n]에서 거꾸로 따라갑니다 — 글자가 같으면 대각선으로 이동하며 그 글자를 기록하고, 다르면 더 큰 쪽으로 이동합니다.
알고노트 시각화는 표가 채워지고, 글자가 일치할 때 대각선이 강조되는 과정을 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(mn) |
| 공간 | O(mn) |
m, n은 두 수열의 길이입니다. 길이만 필요하면 두 행만 굴려 공간을 O(n)으로 줄일 수 있습니다.
예시로 따라가기
A = ABCBDAB, B = BDCAB를 비교하면
- •공통으로 순서를 지키며 뽑을 수 있는 가장 긴 것은
BCAB(또는BDAB) — 길이 4 - •표의 오른쪽 아래 칸 값이 4가 됩니다
연속이 아니어도 됨에 주의하세요 — B, C, A, B가 떨어져 있어도 순서만 맞으면 됩니다.
자주 하는 실수
- •부분 문자열과 혼동: LCS는 연속을 요구하지 않습니다. 연속이 필요하면 "최장 공통 부분 문자열"이라는 다른 문제입니다.
- •인덱스 경계: 0번째 행/열(빈 문자열)을 두지 않으면
dp[i-1]참조에서 어긋납니다. - •복원 방향: 같을 때 대각선, 다를 때 큰 쪽 — 방향을 헷갈리면 엉뚱한 수열이 복원됩니다.
알고노트에서 직접 확인하세요
두 수열의 글자를 비교하며 표가 채워지고, 일치할 때 길이가 늘어나는 과정을 알고노트에서 단계별로 확인할 수 있습니다.