편집 거리(Levenshte인)
삽입·삭제·교체 연산의 편집 거리 점화식을 도출하고 길이가 다양한 문자열 쌍에 대한 DP 표를 작성합니다.
편집 거리(Levenshte인)은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
편집 거리 문제
편집 거리(레벤슈타인 거리, LeetCode 72)는 한 문자열을 다른 문자열로 변환하는 데 필요한 삽입, 삭제 또는 교체 연산의 최소 횟수를 묻습니다. 예를 들어 'horse'를 'ros'로 변환하려면 'h'→'r'로 교체(horse→rorse), 'r'을 삭제(rorse→rose), 'e'를 삭제(rose→ros)하여 3번의 연산이 필요합니다. 편집 거리는 철자 검사기, DNA 정렬 및 퍼지 매칭의 기반이 됩니다.
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')DP 상태와 점화식
dp[i][j]를 word1[:i]과 word2[:j] 사이의 최소 편집 거리로 정의합니다. word1[i-1] == word2[j-1]이면 연산이 필요하지 않으므로 dp[i][j] = dp[i-1][j-1]입니다. 그렇지 않으면 세 연산의 최솟값을 취합니다. 삽입 dp[i][j-1] + 1, 삭제 dp[i-1][j] + 1, 교체 dp[i-1][j-1] + 1입니다. 기본 조건은 dp[i][0] = i(word1의 모든 문자 삭제)와 dp[0][j] = j(word2의 모든 문자 삽입)입니다.
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
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] # no cost
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1] # replace
)
return dp[m][n]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5세 연산 이해하기
세 연산은 DP 표에서의 이동과 직접 대응합니다. 교체 dp[i-1][j-1]+1 — 두 문자를 모두 맞추었지만 비용 1을 지불합니다. word1에서 삭제 dp[i-1][j]+1 — word1에서 문자 하나를 제거하므로 표에서 위로 이동합니다. word1에 삽입 dp[i][j-1]+1 — word2의 문자와 맞추기 위해 문자를 삽입하므로 왼쪽으로 이동합니다. 세 값 중 최솟값이 최적의 편집 경로를 결정합니다.
# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]
word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
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 word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print(' ', ' '.join(' '+word2))
for i, row in enumerate(dp):
print((' ' if i==0 else word1[i-1]), row)O(n)으로 공간 최적화
편집 거리에는 현재 행과 이전 행만 필요합니다. 크기가 n+1인 1차원 배열을 사용하고, 각 셀을 갱신하기 전에 diagonal 값(dp[i-1][j-1])을 별도로 추적합니다. 왼쪽에서 오른쪽으로 처리합니다. temp = dp[j](이전 값 = dp[i-1][j])를 저장한 다음, dp[j](삭제), dp[j-1](삽입), diagonal(교체)을 사용하여 dp[j]를 갱신합니다.
def edit_distance_1d(word1, word2):
m, n = len(word1), len(word2)
dp = list(range(n + 1)) # initial row: 0,1,2,...,n
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j] before overwrite
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], # delete
dp[j-1], # insert
diag) # replace
diag = temp
return dp[n]
print(edit_distance_1d('horse', 'ros')) # 3
print(edit_distance_1d('intention', 'execution')) # 5편집 연산 복원
실제 편집 순서를 복원하려면 (m, n)에서 DP 표를 역추적합니다. 각 셀에서 word1[i-1] == word2[j-1]이면 대각선으로 이동합니다(연산 없음). 그렇지 않으면 세 이웃 중 최솟값을 제공한 이웃을 찾아 해당 연산을 기록합니다. 이렇게 하면 편집 스크립트가 역순으로 생성되므로 최종 답을 위해 순서를 뒤집습니다.
def edit_ops(word1, word2):
m, n = len(word1), len(word2)
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 word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
ops, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and word1[i-1]==word2[j-1]:
i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
else:
ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
return list(reversed(ops))
for op in edit_ops('horse', 'ros'): print(op)편집 한 번인지 확인
더 간단한 면접 문제는 두 문자열의 편집 거리가 정확히 1인지 확인하는 것입니다. 이 문제는 DP 없이 O(n)에 해결할 수 있습니다. 두 문자열을 동시에 순회합니다. 불일치가 발생하면 세 연산을 모두 시도합니다(s1에서 문자 하나 건너뛰기, s2에서 문자 하나 건너뛰기, 두 문자열에서 모두 문자 하나 건너뛰기). 그런 다음 남은 부분이 동일한지 확인합니다. 불일치가 두 번 발생하면 거짓을 반환합니다. 이 탐욕적 방법을 사용하면 거리가 ≤ 1인지 확인하는 경우 전체 O(mn) DP를 사용하지 않아도 됩니다.
def is_one_edit_distance(s, t):
m, n = len(s), len(t)
if abs(m - n) > 1: return False
if m > n: return is_one_edit_distance(t, s) # ensure m <= n
for i in range(m):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:] # replace
else:
return s[i:] == t[i+1:] # insert into s (delete from t)
return m + 1 == n # all matched, lengths differ by 1
print(is_one_edit_distance('ab', 'acb')) # True (insert c)
print(is_one_edit_distance('ab', 'ab')) # False (zero edits)
print(is_one_edit_distance('ab', 'abc')) # True (append c)
print(is_one_edit_distance('ab', 'xyz')) # False편집 거리와 LCS 비교
세 연산을 모두 사용하는 편집 거리와 LCS는 문자열 유사성을 서로 다른 관점에서 보여 줍니다. 편집 거리는 차이를 세고, LCS는 유사성을 셉니다. 삽입과 삭제만 허용하고 교체는 허용하지 않을 때 편집 거리는 m + n - 2×LCS입니다. 치환을 허용하면 DP가 약간 달라집니다. 일치할 때 대각선 값은 dp[i-1][j-1]을 기여하고(비용 없음), 교체할 때는 dp[i-1][j-1]+1을 기여합니다. 두 알고리즘 모두 O(mn) 시간에 실행됩니다.
def lcs_len(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 edit_insert_delete_only(s1, s2):
return len(s1) + len(s2) - 2 * lcs_len(s1, s2)
print(edit_insert_delete_only('sea', 'eat')) # 2
print(edit_distance('sea', 'eat')) # 2 (same here: replace not needed)퍼지 문자열 매칭
편집 거리는 실제 세계의 퍼지 매칭을 가능하게 합니다. 철자 검사기는 입력한 단어와 편집 거리가 1 또는 2 이내인 수정안을 제안합니다. 대규모 환경에서의 문제는 O(mn × dict_size) 비교를 피하는 것입니다. 해결 방법으로는 BK-트리(편집 거리를 위한 거리 트리), n-그램 색인, 비탭과 같은 근사 문자열 매칭 알고리즘이 있습니다. 기반이 되는 DP를 이해하면 이러한 상위 수준 도구의 효율성을 판단하는 데 도움이 됩니다.
def spell_suggest(typed, dictionary, max_dist=2):
'''Return words in dictionary within max_dist edits of typed.'''
suggestions = []
for word in dictionary:
if abs(len(typed) - len(word)) <= max_dist:
if edit_distance(typed, word) <= max_dist:
suggestions.append(word)
return suggestions
def edit_distance(w1, w2):
dp = list(range(len(w2)+1))
for i,c1 in enumerate(w1,1):
prev = i
for j,c2 in enumerate(w2,1):
temp = dp[j]
dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
prev = temp
return dp[len(w2)]
dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary)) # horse, worse, house, morse가중 편집 거리
일부 응용 분야에서는 연산마다 비용이 다릅니다. 예를 들어 인접한 문자의 위치를 바꾸는 연산(흔한 오타)은 완전한 교체보다 비용이 적을 수 있습니다. 다메라우-레벤슈타인 거리는 네 번째 연산으로 전치를 추가합니다. DP는 다음 조건에서 dp[i-2][j-2]+1도 확인하도록 확장됩니다. word1[i-1]==word2[j-2]이고 word1[i-2]==word2[j-1]이어야 합니다. 이를 통해 키보드 오타를 더 정확하게 모델링할 수 있습니다.
def damerau_levenshtein(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):
cost = 0 if s[i-1]==t[j-1] else 1
dp[i][j] = min(
dp[i-1][j]+1, # delete
dp[i][j-1]+1, # insert
dp[i-1][j-1]+cost # replace
)
# Transposition
if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
return dp[m][n]
print(damerau_levenshtein('CA', 'ABC')) # 2
print(damerau_levenshtein('ab', 'ba')) # 1 (transposition)DNA 서열 정렬
생물정보학에서는 DNA 서열 정렬에 편집 거리 변형 알고리즘을 사용합니다. Needleman-Wunsch 알고리즘은 LCS 및 편집 거리와 밀접한 관련이 있는 전역 정렬 DP입니다. 일치에는 +1, 불일치에는 -1, 갭(삽입/삭제)에는 벌점을 부여합니다. 스미스-워터먼 변형은 지역 정렬을 수행하여 가장 잘 일치하는 부분 문자열을 찾습니다. 두 알고리즘 모두 동일한 표 작성 구조를 사용하는 O(mn) DP 알고리즘입니다.
def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
m, n = len(seq1), len(seq2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i * gap
for j in range(n+1): dp[0][j] = j * gap
for i in range(1,m+1):
for j in range(1,n+1):
score = match if seq1[i-1]==seq2[j-1] else mismatch
dp[i][j] = max(
dp[i-1][j-1] + score, # align
dp[i-1][j] + gap, # gap in seq2
dp[i][j-1] + gap # gap in seq1
)
return dp[m][n]
print(needleman_wunsch('GATTACA', 'GCATGCU')) # alignment score편집 거리 문제의 면접 풀이법
면접에서 편집 거리 문제를 받으면 다음과 같이 접근하십시오. (1) 허용되는 연산(삽입/삭제/교체)을 확인하십시오. (2) DP 상태를 명확하게 정의하십시오. (3) 세 가지 경우와 점화식을 명시적으로 작성하십시오. (4) 기본 조건인 dp[i][0]=i와 dp[0][j]=j를 제시하십시오. (5) O(n) 공간 최적화를 언급하십시오. (6) 시간이 허락한다면 'cat'→'cut'(교체 1회)과 같은 간단한 예를 따라가며 검증하십시오. O(mn) 시간 및 O(mn) → O(n) 공간이 표준적인 복잡도 경계입니다.
# Clean interview solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
# O(n) space with rolling row
dp = list(range(n + 1))
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0]
dp[0] = i
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = diag
else:
dp[j] = 1 + min(dp[j], dp[j-1], diag)
diag = temp
return dp[n]
# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros')) # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc')) # 3
print(min_distance('abc', '')) # 3빠른 확인
이 레슨의 자료 구조 및 알고리즘 & 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
레슨 요약
이 레슨에서는 다음을 배웠습니다. 편집 거리는 dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost)이고, 일치하면 cost=0, 아니면 1입니다. 또한 기본 조건 dp[i][0]=i와 dp[0][j]=j는 빈 문자열로 변환하거나 빈 문자열에서 변환하는 과정을 나타냅니다. 그리고 O(n) 공간 최적화는 대각선 변수를 사용하는 순환 1차원 배열을 활용합니다. 다음으로 동일한 순환 배열 기법을 적용하여 2D DP 표의 공간을 O(mn)에서 O(min(m,n))으로 줄입니다.
자주 묻는 질문
“편집 거리(Levenshte인)” 강의는 무료인가요?
네 — “편집 거리(Levenshte인)” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“편집 거리(Levenshte인)”에서 뭘 배우나요?
삽입·삭제·교체 연산의 편집 거리 점화식을 도출하고 길이가 다양한 문자열 쌍에 대한 DP 표를 작성합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“편집 거리(Levenshte인)” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 격자의 고유 경로와 최소 경로 합
- 최장 공통 부분 수열
- 편집 거리(Levenshte인)
- 2차원 DP 공간 최적화