알고리즘 공부 - 동적 계획법 2 (두 문자열 사이의 거리)

1. 두 문자열 사이의 거리

두 문자열 s1, s2가 주어진다. 이제 s1에서 문자 하나를 추가하거나 제거할 수 있으며, 이를 반복함으로써 s2를 얻고싶다고 하자. 예를 들어, s1 = “abc”, s2 = “bdcf” 라고 하면, s1에서 a를 제거하고 d를 추가, 그리고 f를 추가하면 s2를 얻을 수 있다. 즉, 다음과 같은 경로로 s1에서 s2를 얻을 수 있다.
“abc” -> “bc” -> “bdc” -> “bdcf”
두 문자열 s1, s2 사이의 거리란, s1에서 s2를 만들기 위해 필요한 문자 삽입, 삭제 횟수의 최소값으로 정의된다. 예를 들어, s1 = “abc”, s2 = “bdcf”라면, 두 문자열의 거리는 3이다. 왜냐하면, s1에서 문자의 추가 및 삭제를 3번 하면 s2를 얻을 수 있기 때문이며, 이보다 더 적은 연산을 통해서는 s2를 얻을 수 없다.
두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오.

입력: 첫 번째 줄에 문자열 s1, 두 번째 줄에 문자열 s2가 주어진다. 문자열의 길이는 2000을 넘지 않는다.

출력: 두 문자열 사이의 거리를 출력한다.

입력 예시:
abc
bdcf

출력 예시: 3

 

def strDistance(s1, s2) 
    
    m = len(s1)
    n = len(s2)
    table = [[0 for _ in range (m+1)] for _ in range (n+1)]
    for i in range(1, m+1):
        table[0][i] = i
    for i in range(1, n+1):
        table[i][0] = i
        
    for i in range(1, n+1):
        for j in range(1, m+1):
            if (s1[j-1] == s2[i-1]):
                table[i][j] = table[i-1][j-1]
                #비교하는 문자가 같을 경우 왼쪽위 칸의 값을 가져옴
            else:
                table[i][j] = min(table[i-1][j], table[i][j-1]) + 1
                #아니라면 왼쪽이나 위 중 작은 값을 가져와 1을 더해줌
                
    return table[-1][-1]

 

	" "	a	b	c
" "	0	1	2	3
b	1	2	1	2
d	2	3	2	3
c	3	4	3	2
f	4	5	4	3

1. 가로 첫 번째 줄 의미:

0에서 a가려면 1번,

0에서 ab가려면 2번,

0에서 abc가려면 3번

 

2. 세로 첫 번째 줄 의미:

0에서 b가려면 1번,

0에서 bd가려면 2번,

...

0에서 bdcf가려면 4번

 

3. 가로 두 번째 줄 의미:

b에서 0가려면 1번,

b에서 a가려면 2번,

b에서 ab가려면 1번 (s1[j-1] == s2[i-1] 이기 때문에 왼쪽위 칸의 1을 그대로 가져와서 쓴다)

b에서 abc가려면 2번(왼쪽의 1과 위쪽의 3중 작은 숫자를 골라 1을 더해준다)

 

...

 

요점은 "비교하는 문자가 같을 경우 왼쪽위 칸의 값을 가져오고" 아니면 "왼쪽이나 위 중 작은 값을 골라 1을 더해주면" 된다.