[알고리즘] LCS (최장 공통 부분 수열, Longest Common Subsequence)

LCS란?

**LCS(Longest Common Subsequence)**는 두 문자열에서 순서를 유지한 채로 공통으로 존재하는 가장 긴 부분 수열을 찾는 문제입니다.

• "부분 수열"이란? → 연속하지 않아도 순서만 지키면 됨.
• 예:
  A = ACAYKP
  B = CAPCAK
  LCS = ACAK (길이 4)

 

LCS와 유사한 개념들

부분 문자열	연속된 문자	ACE ❌
부분 수열	순서만 지키면 됨	ACEF ✅
LCS	공통된 부분 수열 중 가장 긴 것	ACEF ✅ (정답)

 

핵심 아이디어: DP로 최적화

정의

dp[i][j] : A의 i번째 문자까지, B의 j번째 문자까지 비교했을 때 LCS의 길이

 

점화식

if A[i] == B[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

문자 일치 → LCS에 추가
문자 불일치 → 하나 버리고 최대값 선택

 

초기화

• dp[0][*] = dp[*][0] = 0
  → 하나가 빈 문자열이라면 공통 수열은 없으니까 0

 

시각적 설명 (표 예시)

''	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 

어떻게 이해하면 좋을까?

1. 비교 순서는 왼쪽 위 → 오른쪽 아래로 진행
2. 문자가 같을 때는 +1, 안 같으면 이전 최대값 유지
3. dp[i][j]는 결국 두 문자열을 여기까지 비교했을 때의 최적값

응용 문제

• LCS 길이 구하기 (기본)
• LCS 문자열 출력하기
• 두 문자열의 편집 거리, 유사도 비교
• Git diff, Bio sequence alignment 등 실전 응용 많음