공부한 내용 기록하기 공부한 내용 기록하기

1. Levenshtein Distance란?Levenshtein Distance는 두 문자열 간의 유사도(Similarity)를 측정하기 위한 알고리즘으로, 한 문자열을 다른 문자열로 바꾸기 위해 필요한 최소 연산 횟수(편집 거리, Edit Distance)를 계산한다. 이때 허용되는 연산은 다음 세 가지다.문자 삽입 (Insertion)문자 삭제 (Deletion)문자 교체 (Substitution)예를 들어, 문자열 "kitten"을 "sitting"으로 바꾸는 최소 편집 거리는 3이다.k → s (교체)e → i (교체)끝에 g 추가 (삽입)2. 알고리즘의 동작 원리Levenshtein Distance는 동적 계획법(Dynamic Programming)을 활용하여 2차원 배열(dp 테이블)을 구성..