편집거리 알고리즘

편집거리 알고리즘은 아래의 조건에서 이루어진다.

문자열 T1을 T2로 바꾸기 위해서 아래의 연산을 최소 몇번 해야하는가? 

1. 한글자 지우기

2. 한 글자 넣기

3. 한 글자를 다른 글자로 바꾸기

이제 이 알고리즘을 파악하기 위해 두 문자열을 예시로 한번 생각해보자.

VINTNER과 WRITERS가 있다.

VINTNER을 WRITERS로 바꾸기 위해 위의 연산을 최소 몇번 해야하는지 파악해보자.

우선 인덱스를 0이아닌 1번부터 시작시키기 위해 앞에 '0'의 문자를 추가해보자

0VINTNER, 0WRITERS

이제 이 문자열을 표로 나타내보자.

	0	W	R	I	T	E	R	S
0
V
I
N
T
N
E
R

위의 표를 쌓아가는 방법은 다음과 같다.

0WRITERS에서 0이 0VINTNER 순서대로 되기 위해 몇번의 연산이 있어야 하나이다.

즉,

0이 0이 되려면 0번의 연산, 

0이 0V가 되려면 한글자만 넣으면 되기에 1번의 연산

0이 0VI가 되려면 두글자만 넣으면 되기에 2번의 연산

...

0이 0VINTNER이 되기 위해 7번의 연산이 필요하다

이런 방식으로 아래에 모두 채워보자

i ＼ j	0	W	R	I	T	E	R	S
0	0	1	2	3	4	5	6	7
V	1	1	2	3	4	5	6	7
I	2	2	2	2	3	4	5	6
N	3	3	3	3	3	4	5	6
T	4	4	4	4	3	4	5	6
N	5	5	5	5	4	4	5	6
E	6	6	6	6	5	4	5	6
R	7	7	6	7	6	5	4	5

어떻게 이 표를 채우는지 확인해보자.

우선 dp 테이블의 dp[i][j]는 문자열1의 i번째와 문자열2의 j번째까지의 최소 편집 거리를 의미한다.

str1[i] != str2[j]일때는 dp[i][j] = min({dp[i][j-1], dp[i-1][j], dp[i-1][j-1]}) + 1이 된다.

그 의미는 현재까지 최소 편집거리를 유지해온 좌측, 위측, 왼쪽대각위측에서 하나만 변경하거나 삽입하면 되므로 + 1을 가지게 된다.

str1[i] == str2[j] 일때는 편집할 것이 없으므로 dp[i][j] = dp[i-1][j-1]을 가져오면 된다. (즉, i도 다음칸, j도 다음칸으로 가겠다는 의미가 된다.)

* 이 알고리즘은 LCS 알고리즘과 함께 공부하면 좋다고 생각된다 *

아래는 편집거리 알고리즘을 이용하여 풀 수 있는 문제이다.

[15483번] 최소 편집 :: https://www.acmicpc.net/problem/15483

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
int dp[1001][1001];
int main()
{
    string a, b;
    cin >> a >> b;
 
    a.insert(a.begin(), '0');
    b.insert(b.begin(), '0');
 
    int len1 = a.size();
    int len2 = b.size();
 
    for (int i = 0; i < len1; ++i)
        dp[i][0] = i;
    for (int i = 0; i < len2; ++i)
        dp[0][i] = i;
 
    for (int i = 1; i < len1; ++i)
        for (int j = 1; j < len2; ++j)
        {
            if (a[i] == b[j])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = min({ dp[i - 1][j - 1],dp[i][j - 1],dp[i - 1][j] }) + 1;
        }
 
    printf("%d", dp[len1 - 1][len2 - 1]);
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>