1. 편집 거리 문제

소스 문자열을 타겟 문자열로 수정하는데 걸리는 연산의 갯수
연산은 삽입, 삭제, 수정 3가지가 있다

1.1 최소 편집 횟수

아래 사진은 삽입 1번 삭제 2번 대체 1번으로
총 4번의 연산이 이루어져 편집거리 4를 갖는다.
strong -> stone

하지만 편집거리를 아래와 같이 2번으로 줄일 수 있다.

이렇게 최소한의 연산을 통해해 타겟 문자열로 변경하는것을 최소 편집 횟수라고 한다.

1.2 최소 편집 횟수

편집거리 알고리즘

for i=0 to m E[i,0]=i
for j=0 to n E[0,j]=j

for i = 1 to m
	for j = 0 to n
    	E[i,j] = min{E[i, j-1]+1, E[i-1, j]+1, E[i-1, j-1]+a}
return E[m,n]

위 알고리즘을 따라서 표의 빈칸을 채워나가면 아래의 표가 나온다.

문자열 strong을 문자열 stone로 수정하는데 연산은 총 2번 필요하다.

소스 문자열의 길이 m
타겟 문자열의 길이 n
시간복잡도 O(mn)