동적 프로그래밍으로 푸는 LCS·편집 거리·행렬 연쇄 곱
LCS, Edit Distance, Matrix Chain Multiplication의 상태 정의와 전이식, 복원 방식, 공간 최적화와 코드 구현을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
같은 DP 테이블이 해결하는 서로 다른 최적화 문제
LCS, Edit Distance, Matrix Chain Multiplication은 모두 입력을 작은 부분문제로 나누고, 계산 결과를 테이블에 쌓아 최적값을 구한다. 다만 각 문제에서 테이블이 의미하는 값과 복원해야 하는 결과는 다르다.
LCS(Longest Common Subsequence)는 두 시퀀스에 공통으로 포함되는 부분수열 가운데 가장 긴 길이를 찾는다. 전형적인 상태는 dp[i][j] = s1[:i], s2[:j]의 LCS 길이다.
s1[i-1] == s2[j-1]이면dp[i][j] = dp[i-1][j-1] + 1- 그렇지 않으면
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Edit Distance, 즉 Levenshtein Distance는 한 문자열을 다른 문자열로 바꾸기 위한 최소 편집 횟수를 구한다. 편집 연산은 삽입, 삭제, 치환이다. 상태는 dp[i][j] = s1[:i] → s2[:j] 최소 편집 비용으로 둘 수 있다.
s1[i-1] == s2[j-1]이면dp[i][j] = dp[i-1][j-1]- 그렇지 않으면
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
Matrix Chain Multiplication(MCM)은 행렬의 곱셈 순서를 바꿔 스칼라 곱 연산 수를 최소화하는 문제다. m[i][j]는 Ai…Aj를 곱하는 최소 비용이고, s[i][j]에는 분할 위치를 기록한다.
m[i][i] = 0m[i][j] = min over k∈[i, j-1] of m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
상태의 경계와 채우는 순서가 결과를 좌우한다
LCS는 dp[i][0]=dp[0][j]=0으로 시작한다. Edit Distance는 빈 문자열과의 변환 비용을 반영해 dp[i][0]=i, dp[0][j]=j로 초기화한다. MCM은 대각 원소를 0으로 두고 나머지 값을 무한대로 초기화한다.
LCS와 Edit Distance는 i, j를 각각 1→n, 1→m 순서로 진행하면 이전 상태에 안전하게 접근할 수 있다. MCM은 체인 길이 L=2→n 순으로 순회해야 더 짧은 구간의 계산이 먼저 끝난다.
복원이 필요할 때도 저장해야 할 정보가 달라진다. LCS는 역추적으로 공통 부분수열을 복원하고, Edit Distance는 삽입·삭제·치환의 연산 시퀀스를 복원할 수 있다. MCM은 s 테이블을 따라가며 최적 괄호 배치를 재구성한다.
LCS와 Edit Distance는 롤링 배열을 적용하면 메모리를 O(min(n,m))까지 줄일 수 있다. Hirschberg는 LCS의 공간을 줄이고, Myers는 Edit Distance의 공간과 시간을 개선할 수 있지만 구현 복잡도가 올라간다. MCM은 복원을 위해 s 테이블을 유지할 경우 O(n^2) 공간이 필요하다.
문자열 비교와 행렬 연산에서의 처리 방식
LCS는 문자열 s1, s2를 입력으로 받아 O(nm) DP 테이블을 채운다. 값이 같은 후보가 여러 개일 때는 tie-breaking 규칙을 고정해야 동일 입력에서 재현 가능한 시퀀스를 얻을 수 있다. 결과는 LCS 길이이며, 필요하면 공통 부분수열도 함께 복원한다.
Edit Distance는 문자열과 함께 치환 비용이나 밴드 폭 k 같은 옵션을 받을 수 있다. 기본 복잡도는 O(nm)이고, 허용 거리 k가 작으면 밴드 DP로 O(k·min(n,m)) 근사를 적용할 수 있다. 최소 편집 거리와 선택적으로 편집 연산열을 반환한다.
MCM의 입력은 차원 배열 p[0…n]이며, 행렬 Ai의 크기는 p[i-1]×p[i]다. 체인 길이를 늘려 가며 최소 비용의 분할점을 기록하고, 최종적으로 최소 스칼라 곱 수와 괄호 배치를 얻는다.
적용 맥락과 비용 차이
LCS는 소스 코드 diff와 버전 비교 자동화, 바이오인포매틱스의 서열 유사도 기초 지표 산출과 정렬 전 필터링, 로그·이벤트 스트림의 패턴 유사도 측정에 활용할 수 있다.
Edit Distance는 오타 교정과 검색 자동완성 후보 랭킹, 전자상거래 상품명·주소 정규화의 퍼지 매칭, 데이터 통합 과정의 키 정합성 검증과 클러스터링에 맞는다.
MCM은 데이터베이스 쿼리 최적화에서 조인 순서와 곱셈 순서를 근사하거나, 선형대수 루틴의 연산 순서를 최적화해 캐시 적중률을 높이는 데 사용한다. 컴파일러와 딥러닝 런타임의 연산 그래프 괄호 배치 힌트에도 연결된다.
차원 배열이 p=[10,100,5,50]일 때 (A·B)·C의 비용은 10×100×5 + 10×5×50 = 7,500이다. 반면 A·(B·C)는 100×5×50 + 10×100×50 = 75,000으로 계산되며, 최적 대비 비최적 10배 연산 차이가 난다.
허용 거리 k=2, 길이 200인 Edit Distance에 밴드 DP를 적용하면 계산 셀 수는 약 200×5=1,000로 축소된다. 기본 40,000과 비교하면 97.5% 감소다. 롤링 배열은 메모리 사용을 O(nm)→O(min(n,m))으로 줄이며, 결정적 결과는 테스트와 회귀 검증에도 유리하다.
문제별 복잡도와 운영상 고려점
| 문제 | 시간 복잡도 | 공간 복잡도 | 확장성 | 일관성 | 안정성 | 운영 편의 |
|---|---|---|---|---|---|---|
| LCS | O(nm) | O(nm), 롤링 O(min(n,m)) | Bitset/Hirschberg로 대규모 처리 일부 가속 | 결정적 결과 | Tie-breaking 규칙 필요 | 복원 시 O(n+m) 추가 처리 |
| Edit Distance | O(nm), 밴드 O(k·min(n,m)), Myers 평균 선형 | O(nm), 롤링 O(min(n,m)) | 길이 불균형 시 밴드/비트벡터로 확장 | 결정적 결과 | 비용 모델 일관성 필요 | 임계값 기반 조기 중단 용이 |
| MCM | O(n^3) | O(n^2) | n>500 시 근사/휴리스틱 고려 필요 | 결정적 결과 | 비용 모델 정확도 중요 | 최적 괄호 출력으로 디버그 용이 |
실행 가능한 Python 구현
전제조건: Python 3.10+, 표준 라이브러리만
LCS 구현에서는 위 우선 규칙으로 동률을 처리하고, 채워진 테이블을 역방향으로 따라가며 시퀀스를 만든다.
def lcs(s1: str, s2: str):
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
si = s1[i-1]
for j in range(1, m+1):
if si == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
# tie-breaking: 위 우선
dp[i][j] = dp[i-1][j] if dp[i-1][j] >= dp[i][j-1] else dp[i][j-1]
# backtrack
i, j = n, m
seq = []
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
seq.append(s1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] >= dp[i][j-1]:
i -= 1
else:
j -= 1
return dp[n][m], ''.join(reversed(seq))
if __name__ == "__main__":
print(lcs("ABCBDAB", "BDCAB")) # (4, 'BCAB') 등 동률 규칙에 따라 동일 길이 시퀀스Edit Distance 구현은 max_dist가 주어진 경우 밴드 범위 안에서만 테이블을 계산한다. 임계값을 넘으면 조기 반환한다.
def edit_distance(s1: str, s2: str, max_dist: int | None = None) -> int:
n, m = len(s1), len(s2)
if n == 0: return m
if m == 0: return n
# 밴딩: 허용 거리가 작을 때 유효
band = max_dist if max_dist is not None else max(n, m)
INF = 10**9
dp = [[INF]*(m+1) for _ in range(n+1)]
for i in range(n+1):
jmin, jmax = max(0, i-band), min(m, i+band)
if jmin == 0: dp[i][0] = i
for j in range(jmin, jmax+1):
if i == 0:
dp[0][j] = j
else:
cost = 0 if s1[i-1] == s2[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # 삭제
dp[i][j-1] + 1, # 삽입
dp[i-1][j-1] + cost # 치환
)
if max_dist is not None and min(dp[i][max(0, i-band):min(m, i+band)+1]) > max_dist:
return max_dist + 1 # 조기 중단(임계 초과)
return dp[n][m]
if __name__ == "__main__":
print(edit_distance("kitten", "sitting")) # 3
print(edit_distance("abcdef", "azced", max_dist=2)) # 3(>2) → 3 또는 3보다 크면 조기 반환MCM 구현은 최소 비용과 분할 위치를 함께 기록한다. build 함수는 저장된 분할 위치를 사용해 괄호 배치를 복원한다.
def matrix_chain_order(p: list[int]):
n = len(p) - 1
INF = 10**18
m = [[0 if i == j else INF for j in range(n)] for i in range(n)]
s = [[-1]*n for _ in range(n)]
for L in range(2, n+1): # 체인 길이
for i in range(0, n-L+1):
j = i + L - 1
for k in range(i, j):
cost = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]
if cost < m[i][j]:
m[i][j] = cost
s[i][j] = k
def build(i: int, j: int) -> str:
if i == j: return f"A{i+1}"
k = s[i][j]
return f"({build(i, k)}×{build(k+1, j)})"
return m[0][n-1], build(0, n-1)
if __name__ == "__main__":
cost, order = matrix_chain_order([10,100,5,50])
print(cost, order) # 7500, ((A1×A2)×A3)데이터 규모에 따라 달라지는 선택
대규모 문자열이 수백만 길이라면 LCS에는 Hirschberg를 적용해 메모리를 줄이고, Edit Distance에는 Myers 비트벡터 방식을 검토할 수 있다. MCM은 n^3 한계를 고려해야 하므로 탐욕적·근사 방식인 지역 최적 병합과 비용 모델 보정을 함께 검토한다.
Edit Distance의 밴드 설정은 오탐과 미탐의 트레이드오프를 만들기 때문에 검색 임계값과 맞춰야 한다. LCS 길이만 필요하다면 복원 과정을 생략해 메모리와 시간을 줄일 수 있다.
동률 처리 규칙을 고정하면 결과 재현성을 확보할 수 있다. 빈 문자열과 차원 불일치 같은 입력은 미리 검증하고, overflow나 메모리 부족 상황에서는 롤링 배열과 스트리밍 전략을 적용한다. 데이터 규모가 크거나 비용 모델이 복잡할수록 DP 정확 탐색과 휴리스틱을 섞는 하이브리드 전략이 필요하다.