토픽 37 / 82

편집 거리 (Edit Distance, Levenshtein Distance)

한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 연산(삽입, 삭제, 치환) 횟수를 구하는 동적 프로그래밍 문제

목적: 문자열 유사도, 철자 검사, DNA 비교

특징: 동적 프로그래밍, 3가지 연산, 2D 테이블

편집 연산: 삽입(Insert), 삭제(Delete), 치환(Replace)

점화식: dp[i][j] = min(dp[i-1][j]+1(삭제), dp[i][j-1]+1(삽입), dp[i-1][j-1]+cost(치환, cost=0 if 같음 else 1))

시간 복잡도: O(mn)

공간 복잡도: O(mn), O(n) 최적화 가능

장점: 정확한 유사도, 다양한 응용, 직관적

단점: O(mn) 시공간, 대규모 문자열 비효율

적용사례: 철자 검사, 검색 엔진(typo 교정), DNA 서열 정렬, 자동 완성, OCR 후처리

비교: 편집 거리(3연산) vs Hamming 거리(같은 길이/치환만)

연관: 동적 프로그래밍, LCS, 문자열, 유사도