happy coding

수업을 듣고 정리한 내용입니다. 편집거리 문제(edit distance)는 문서 편집기를 사용하는 중에 스트링 S를 수정해 다른 T로 변환하고자 할 때, 삽입(insert), 삭제(delete) 그리고 대체(sutstitude) 연산을 사용하는데 필요한 최소 편집 연산횟수를 계산하는 알고리즘이다. 문자를 편집할 때, 어떤 연산을 어느 문자에 수행하느냐에 따라 편집 연산 횟수가 달라지는데, 이를 부분문제를 정의하여 해결한다. 편집거리 문제에서 부분 문제는 접두부(prefix)를 확인하는 과정으로부터 시작된다. S의 길이를 m 그리고 T의 길이를 n이라 하고, 각각의 문자를 s_i, t_i라고 가정하였을 때, S = s1s2s3 ... sm, T = t1t2t3 ... tn이다. E[i,j]를 S의 처음 i..