문자열 DP는 두 문자열 간의 유사도, 최장 공통 부분 수열, 편집 거리 등을 동적 프로그래밍으로 계산하는 기법이다. 생물정보학, 텍스트 편집기, 자연어 처리에서 핵심적으로 사용된다.
최장 공통 부분 수열 (LCS)
두 문자열 X, Y에서 순서를 유지하며 공통으로 뽑을 수 있는 최장 부분 수열.
python
def lcs(X, Y):
m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 역추적으로 실제 LCS 문자열 복원
i, j = m, n
result = []
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
result.append(X[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result)), dp[m][n]
X, Y = "ABCBDAB", "BDCAB"
lcs_str, lcs_len = lcs(X, Y)
print(f"LCS: {lcs_str}, 길이: {lcs_len}") # BCAB, 4
편집 거리 (Edit Distance / Levenshtein)
한 문자열을 다른 문자열로 변환할 때 필요한 최소 편집 연산 횟수 (삽입, 삭제, 교체).
python
def edit_distance(s, t):
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # 삭제
dp[i][j-1], # 삽입
dp[i-1][j-1] # 교체
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3
최장 증가 부분 수열 (LIS)
python
import bisect
def lis_length(arr):
"""이진 탐색 활용 O(n log n)"""
tails = []
for x in arr:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4
문자열 DP 유형 비교
| 문제 | 점화식 | 복잡도 |
|---|
| LCS | dp[i][j] = dp[i-1][j-1]+1 또는 max(↑,←) | O(mn) |
| Edit Distance | dp[i][j] = 0 또는 1+min(↑,←,↖) | O(mn) |
| LIS | 이진 탐색 | O(n log n) |
| 팰린드롬 분할 | dp[i] = min(dp[j]+1) if [j+1..i] 팰린드롬 | O(n²) |
| 문자열 정렬 거리 | Jaro-Winkler 등 | O(mn) |
공간 최적화
LCS와 편집 거리 모두 이전 행만 필요하므로 O(min(m,n)) 공간으로 최적화 가능.
관련 개념
