Loading...

미리보기

전체 60개 스텝 중 18개만 표시

로그인하고 전체 보기

편집 거리 (Edit Distance)

보통

Edit Distance (Levenshtein)

한 문자열을 다른 문자열로 변환하는 최소 연산 횟수를 구합니다.

📊 복잡도

구분	복잡도
최선	O(m×n)
평균	O(m×n)
최악	O(m×n)
공간	O(m×n)

🏷️ 태그

DP문자열2D 테이블

📖 개념 소개

편집 거리(Edit Distance)는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 연산 횟수입니다. 삽입(Insert), 삭제(Delete), 교체(Replace) 세 가지 연산을 사용할 수 있습니다. Levenshtein Distance라고도 불립니다.

1/60

Loading...

✏️편집 거리

"KITTEN"을 "SITTING"로 바꾸려면? 3가지 연산을 사용할 수 있어요: • 삽입 (Insert): 문자 추가 • 삭제 (Delete): 문자 제거 • 교체 (Replace): 문자 바꾸기 최소 몇 번의 연산이 필요할까요?

🔒

기초 학습

편집 거리 (Edit Distance)

정의

편집 거리(Edit Distance)는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 연산 횟수입니다. 삽입(Insert), 삭제(Delete), 교체(Replace) 세 가지 연산을 사용할 수 있습니다. Levenshtein Distance라고도 불립니다.

핵심 특성

✓문자 일치 시: dp[i][j] = dp[i-1][j-1] (비용 0)
✓문자 불일치 시: dp[i][j] = 1 + min(삭제, 삽입, 교체)
✓초기화: dp[0][j] = j (삽입 횟수), dp[i][0] = i (삭제 횟수)
✓역추적으로 실제 연산 순서 복원 가능

시간 복잡도

최선

O(m×n)

평균

O(m×n)

최악

O(m×n)

공간 복잡도

O(m×n)

편집 거리 (Edit Distance) | AlgoNote