Minimum Edit Distance

Edit Distance : 한 스트링이 다른 스트링으로 되기까지 필요한 editing operation의 최소 횟수 editing operation : insertion(1), deletion(1), substitution(2) (괄호 안은 각 operation의 cost, Levenshtein) * Levenshtein은 substitution의 cost를 2로 본다 ∵ insertion(1) + deletion(1) = substitution(2) 모든 distance 계산하기 어려움. 그래서 Dynamic Programming 도입 Dynamic Programming - 복잡한 계산 = subproblems를 합쳐서 구해가기 - bottom-up 방식 예를 들어, INTENTION을 EXECUTI..

2019.12.04