최소 편집 거리(edit distance)를 구하는 알고리즘

1. 문제 두 문자열 S1, S2가 주어질때, 다음과 같은 3가지 연산을 임의의 횟수만큼 실행할 수 있다. 1) 임의의 위치에 원하는 문자 하나를 삽입 예: banana >>> banacna 2) 임의의 위치에 있는 문자 하나를 삭제 예: banana >>> banna 3) 임의의 위치에 있는 문자 하나를 원하는 문자로 대체 예: banana >>> canana  2. 재귀를 이용한 해법 문자열의 왼쪽이나 오른쪽 끝에서부터 한문자씩 처리한다. 왼쪽부터 처리해서, 첫번째 문자가 서로 일치하는 경우, 나머지 문자에 대해 재귀적으로 처리 첫번째 문자가 서로 일치하지 않는다면, 여기에 3가지 작업으로 삽입, 제거, 대체 작업을 수행할 수 있다. 그리고 나머지 부분에 대해 재귀적으로 계산  첫번째 문자가 일치하면..