편집 거리 시각화
두 문자열 간 최소 편집 연산(삽입·삭제·치환)을 DP 테이블로 단계별 학습하세요
동적 프로그래밍★★☆
속도
1 / 1 현재 셀 일치 치환 삭제 삽입
DP 테이블이 채워지고 역추적으로 편집 연산이 결정되는 과정을 관찰하세요.
DP 테이블이 채워지고 역추적으로 편집 연산이 결정되는 과정을 관찰하세요.
편집 거리란?
두 문자열을 같게 만드는 최소 편집 연산(삽입, 삭제, 치환) 횟수입니다. Levenshtein Distance라고도 하며, 맞춤법 검사, 유사도 측정에 널리 사용됩니다.
사용 방법
- 1두 문자열을 입력하고 계산 버튼을 클릭하세요
- 2DP 테이블이 채워지는 과정을 단계별로 관찰하세요
- 3역추적 경로로 실제 편집 연산을 확인할 수 있습니다
- 4다양한 문자열 쌍으로 실험해보세요
동작 원리
- 1dp[i][j] = 문자열A의 i글자를 문자열B의 j글자로 바꾸는 최소 비용
- 2A[i]==B[j]이면 dp[i][j] = dp[i-1][j-1] (무료)
- 3아니면 dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) — 삭제, 삽입, 치환 중 최소
- 4시간·공간 복잡도 O(m×n), m과 n은 각 문자열 길이
실무 활용
- •검색엔진의 '이것을 찾으셨나요?' 오타 교정
- •Git diff의 텍스트 차이 비교 알고리즘
- •생물정보학 — DNA/단백질 서열 정렬(Needleman-Wunsch)
- •자연어 처리의 문자열 유사도 측정
비슷한 알고리즘
- •LCS — 공통 부분수열을 찾는 문제, 편집 거리와 관계: ED = m + n - 2×LCS
- •Damerau-Levenshtein — 인접 문자 전치(transposition)도 허용
- •Hamming 거리 — 같은 길이 문자열에서 다른 위치 수만 셈
학습 팁
- •3~4글자 문자열부터 시작하여 테이블을 손으로 채워보세요
- •역추적 경로를 따라가며 각 셀의 선택 이유를 이해하세요
- •LCS와의 관계식을 직접 검증해보세요
자주 묻는 질문
Q. 공간 최적화가 가능한가?
A. 네, 이전 행만 유지하면 O(min(m,n)) 공간으로 가능합니다. 단, 역추적은 불가합니다.
Q. 가중치를 다르게 줄 수 있나?
A. 네, 삽입/삭제/치환 비용을 다르게 설정하면 일반화된 편집 거리가 됩니다.