×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

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


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

1. 한글자 지우기

2. 한 글자 넣기

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


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


VINTNER과 WRITERS가 있다.


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


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


0VINTNER, 0WRITERS


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


 

0

W

R

I

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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 >>
Crocus









반응형
  1. ㅇㅇ 2018.09.20 17:21

    항상 잘보고 갑니다. 자세한 설명 감사합니다.