최장 공통 부분 수열
두 문자열의 LCS 점화식을 정의하고 2차원 표를 채운 뒤, 표를 역추적해 실제 부분 수열을 복원합니다.
최장 공통 부분 수열은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
부분 수열이란
문자열의 부분 수열은 일부 문자를 삭제하거나 아무 문자도 삭제하지 않되, 남은 문자의 순서는 바꾸지 않아 만들어집니다. 예를 들어 'ACE'는 'ABCDE'의 부분 수열이지만 'AEC'는 아닙니다(순서가 어긋납니다). 두 문자열의 최장 공통 부분 수열(LCS)은 두 문자열에 모두 나타나는 가장 긴 부분 수열입니다. 'ABCBDAB'와 'BDCABA'의 공통 LCS는 길이가 4인 'BCBA' 또는 'BDAB'입니다.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueLCS 점화식 유도
dp[i][j]를 text1[:i]와 text2[:j]의 LCS 길이로 정의합니다. 문자가 일치하면(text1[i-1] == text2[j-1]) LCS를 1만큼 늘립니다: dp[i][j] = dp[i-1][j-1] + 1. 일치하지 않으면 두 문자열 중 하나에서 문자를 건너뛰는 경우 중 더 나은 것을 선택합니다: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). 기본 사례는 dp[0][j] = dp[i][0] = 0입니다(빈 문자열과 LCS를 구하면 0입니다).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2LCS 표 추적
text1='ABCD'와 text2='ACBD'인 경우를 보겠습니다. 먼저 모든 칸을 0으로 시작합니다. 문자가 일치하면(A-A, C-C, 올바른 위치의 B-B, D-D) dp[i][j] = dp[i-1][j-1] + 1을 적용합니다. 일치하지 않으면 왼쪽과 위쪽 이웃 중 최댓값을 선택합니다. 채워진 표를 따라가면 대각선 이동이 일치하는 문자에 대응한다는 것을 알 수 있습니다. 최종 값인 dp[4][4]가 LCS 길이를 나타냅니다.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')실제 LCS 복원
실제 LCS 문자열을 복원하려면 dp[m][n]에서 DP 표를 역추적합니다. text1[i-1] == text2[j-1]이면 이 문자는 LCS에 포함되므로 기록한 다음 (i-1, j-1)로 대각선 방향으로 이동합니다. dp[i-1][j] > dp[i][j-1]이면 위로 이동하고, 그렇지 않으면 왼쪽으로 이동합니다. 역추적했기 때문에 마지막에 수집한 문자 순서를 뒤집습니다. 이 복원 과정은 O(m+n) 시간에 실행됩니다.
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABO(n)으로 공간 최적화
LCS 표에는 현재 행과 이전 행만 필요합니다. 크기가 n+1인 1차원 배열과 diagonal 변수를 사용하여, 덮어쓰기 전에 dp[i-1][j-1]에 있던 값을 저장할 수 있습니다. 각 행은 왼쪽에서 오른쪽으로 순회합니다. 각 셀을 처리한 후 갱신된 dp[j]에는 현재 행의 값이 저장되며, 덮어쓰기 전에 이전 값을 diagonal에 저장합니다.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4LCS와 편집 거리의 관계
LCS는 편집 거리(레벤슈타인 거리)와 밀접한 관련이 있습니다. LCS를 알고 있다면 삽입과 삭제만 사용하여 최소 편집 거리를 계산할 수 있습니다: edit_dist = m + n - 2 * LCS(s1, s2). s1에서 LCS에 포함되지 않는 각 문자는 삭제해야 하며, s2에서 LCS에 포함되지 않는 각 문자는 삽입해야 합니다. 여기서는 삽입과 삭제만 허용하므로 치환은 계산하지 않지만, 이 공식은 관련 문제에 유용합니다.
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+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[m][n]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5두 문자열 삭제 연산
두 문자열 삭제 연산(LeetCode 583)은 두 문자열을 같게 만들기 위한 최소 삭제 횟수를 묻습니다. 유지하는 문자들은 공통 부분 수열이어야 하므로 LCS를 최대화하고 나머지는 모두 삭제해야 합니다. 답은 m + n - 2 * LCS(s1, s2)입니다. 이는 앞에서 설명한 삽입/삭제 편집 거리와 같습니다. 문제를 LCS 관점으로 재구성하는 것은 강력한 환원 기법입니다.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[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 = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4최장 공통 부분 문자열
LCS (부분 수열)와 최장 공통 부분 문자열을 혼동하지 마십시오. 부분 문자열은 연속적이므로 문자가 일치하지 않으면 이웃 값 중 최댓값을 취하는 대신 개수를 0으로 초기화합니다. 점화식은 다음과 같이 바뀝니다. 문자가 일치하면 dp[i][j] = dp[i-1][j-1] + 1이고, 그렇지 않으면 dp[i][j] = 0입니다. 모든 셀에서 확인한 최댓값을 추적합니다.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)수열 비교를 위한 LCS
LCS는 파일을 비교하는 diff 도구(유닉스의 diff 등)에 널리 사용됩니다. 두 파일 사이의 편집 스크립트는 LCS에서 도출됩니다. LCS에 포함된 행은 변경되지 않고, 파일 1의 추가 행은 삭제되며, 파일 2의 추가 행은 삽입됩니다. LCS를 이해하면 버전 관리 시스템이 변경 사항을 추적하는 방식과 병합 충돌이 발생하는 이유를 이해하는 데 도움이 됩니다.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)최단 공통 상위 수열
최단 공통 상위 수열(LeetCode 1092)은 s1과 s2를 모두 부분 수열로 포함하는 가장 짧은 문자열을 구하는 문제입니다. LCS의 각 문자는 상위 수열에 한 번만 나타나며, 두 문자열에서 LCS에 속하지 않는 문자들은 모두 포함해야 합니다. 길이 = m + n - LCS(s1, s2)입니다. 복원하려면 동일한 LCS 역추적을 사용하되, 일치하지 않는 위치에서는 두 문자열의 문자를 모두 포함합니다.
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+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])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5LCS의 복잡도와 면접 팁
고전적인 LCS 알고리즘은 O(m×n) 시간 및 O(m×n) 공간에 실행되며, 순환 배열 기법을 사용하면 공간을 O(min(m,n))으로 줄일 수 있습니다. 면접에서 기억할 핵심 사항은 다음과 같습니다. (1) 코딩하기 전에 DP 상태가 무엇을 나타내는지 명확히 정의하십시오. (2) 일치하는 경우와 일치하지 않는 경우를 구분하여 처리하십시오. (3) 수열의 복원을 요청받으면 코딩하기 전에 역추적 방법을 설명하십시오. (4) 인내 정렬을 사용하여 O(n log n)에 해결할 수 있는 관련 1차원 문제인 최장 증가 부분 수열(LIS)을 언급하십시오.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)빠른 확인
이 레슨의 자료 구조 및 알고리즘 & 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
레슨 요약
이 레슨에서는 다음을 배웠습니다. LCS는 일치할 때 dp[i][j] = dp[i-1][j-1]+1을 사용하고, 그렇지 않으면 max(dp[i-1][j], dp[i][j-1])을 사용합니다. 또한 실제 수열은 일치할 때 대각선으로, 불일치할 때 더 큰 이웃을 향해 역추적하여 복원합니다. 그리고 LCS는 편집 거리, 삭제 연산, 최단 공통 상위 수열 및 diff 도구의 기반이 됩니다. 다음으로 LCS 체계에 치환을 추가한 편집 거리(레벤슈타인) 점화식을 도출합니다.
자주 묻는 질문
“최장 공통 부분 수열” 강의는 무료인가요?
네 — “최장 공통 부분 수열” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“최장 공통 부분 수열”에서 뭘 배우나요?
두 문자열의 LCS 점화식을 정의하고 2차원 표를 채운 뒤, 표를 역추적해 실제 부분 수열을 복원합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“최장 공통 부분 수열” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.