편집 거리 문제

편집 거리 문제 (Edit Distance Problem) 문자열 S를 수정하여 문자열 T로 변환하려고 할 때 쓰이는 연산 삽입 - insert 삭제 - delete 대체 - substitude 편집 거리 - S를 T로 변환시키는데 필요한 최소 편집 횟수 편집 거리 예시 S - strong T - stone stong - r 삭제 stone - g → e 대체 총 2회 Idea 각 문자열의 접두부의 편집거리를 미리 알고있으면 부분 문제를 통해 현재를 알 수 있음 stro → sto, ng → ne를 알고 있으면 strong → stone을 알 수 있음 Pseudo code EditDistance Input S: String, T: String 단, S와 T의 길이는 m 과 n Output S를 T로 변환..