[Goldman Sachs 인터뷰] 편집 거리

 

 

 

 

초기 접근

---

글자 하나하나 마다 문자를 수정하는 경우의 수를 구하고 가장 작을때의 경우를 배열에 저장해둔다.

의 문제점 : 가장 작을때가 아니라 같을 때 다음 글자에서 어떤 경우였는지를 알아야한다.

 

그럼 2차원배열에 저장해야하는데 이 3가지 경우의 수를 어떻게 표현할까..

 

 

 

 

 

 

해결 아이디어

---

주어진 단어 두개를 2차원 배열에 표시하면 위치에 따라 3가지 경우의 수로 나눌 수 있다.

예를들어 sunday, saturday 두 단어가 주어졌다고 가정해보자.

 

2차월 배열로 나타내면 아래와 같다.

들어가는 정보는 original 단어에서 new 단어로 바뀔때 최소편집거리를 써준다.

예를들어) dp[0][0] ~ dp[0][8] 까지는 0(아무것도 없는 상태에서) s, sa, sat, satu, satur, ... 로 바뀔때의 최소 편집 거리이다.

index ->	0	1	2	3	4	5	6	7	8
단어 ->	Ø	s	sa	sat	satu	satur	saturd	saturda	saturday
Ø	0	1	2	3	4	5	6	7	8

Ø -> 아무것도 없는상태 의 최소편집거리는 0

Ø -> s 의 최소편집거리는 s 하나만 삽입하면 되니까 1

Ø -> sa 의 최소편집거리는 s와 a 두개를 삽입해야 하니까 2

...

이런식으로 적어주는 것이다.

그래서 초기상태에서는 위와 같은 정보를 담은 2차월 배열이 만들어지는 것이다.

 

그러면 빨간색 네모칸인 dp[1][2]에는 어떤값이 들어가야할까?

dp[1][2]의 의미는 s 가 sa 로 바뀔때의 최소편집거리이다.

 

사람이 직관적으로 판단했을 때는 그냥 a만 추가해주면 되므로 답이 1이라는 것을 쉽게 알 수 있다.

 

이것 과정을 프로그램이 판단하게 하려면 어떻게 해야할까?

 

먼저 프로그램은 해당 자리의 알파벳이 같은지 다른지 판별해야한다.

 

해당 자리의 알파벳이 같으면 아무 변화가 없어도 된다.

그러므로 original, new 단어 둘 다 해당 알파벳 하나 전의 dp 값을 그대로 가져오면 된다. 

그래서 dp[1][1]이 0이 되는 것이다.

dp[1][1]은 변화가 없어도 되어서 0을 넣는 것이 아니라, 변화가 없어도 되니까 알파벳 한칸전 dp[i-1][j-1] (dp[0][0])의 값을 그대로 가져온다.

 

해당 자리의 알파벳이 다르다면 경우의 수를 고려해야한다.

여기서 주의해야할 점은 아래 3가지 경우 모두 다 해당 자리의 문자를 맞출 수 있다.

가장 수가 작을 때를 선택해야 올바른 문제해결이다.

 

예를들어) s -> sa 로 바꿀때 a만 추가 하는 것이 올바른 문제해결 이지만 s에서 x를 추가하고 x를 a로 "교체" 하거나 "삭제"를 해도 문자를 똑같이 맞출 수 있다. 하지만 불필요한 과정이 들어간다. 그렇기 때문에 세가지 경우의 수 중에서 최소를 선택하는 것이 불필요한 과정이 없는 수를 선택하는 것과 같은 의미이다.

 

 

 

1. 알파벳을 삽입하는 경우

dp[i][j-1] 에서 1을 더하는 행위와 같다.

행이 같은 상태에서 오른쪽으로 가므로 열까지에 해당하는 세로문자(표의 왼쪽에 세로로 적어주는 문자)에 한 문자를 더하는 것과 같다.

 

2. 알파벳을 교체하는 경우

dp[i-1][j-1] 에서 1을 더하는 행위와 같다.

행이 하나 늘어났으므로(dp[i-1][j-1] -> dp[i][j]) 세로문자(표의 왼쪽에 세로로 적어주는 문자)가 하나 추가된 상태에서 그 문자를 교체해주는 것과 같은 의미이다.

 

3. 알파벳을 삭제하는 경우

dp[i-1][j] 에서 1을 더하는 행위와 같다.

이것도 행이 하나 늘어났으므로(dp[i][j-1] -> dp[i][j]) 세로문자(표의 왼쪽에 세로로 적어주는 문자)가 하나 추가된 상태에서 그 문자를 삭제해주는 것과 같은 의미이다.

 

 

dp[1][2] 상황에서 예를 들어보자.

 

1) 알파벳을 삽입하는 경우

이 경우는 s -> sa 인 상황에서 s에 a를 추가하는 경우이다.

1번 변했으니 편집거리는 1

 

2) 알파벳을 교체하는 경우

이 경우는 original이 Ø이고 s가 삽입 되어 s가 된 상태에서(Ø -> Øs 현재 편집거리가 1) 오른쪽 아래로 내려가는 것이므로 열의 문자에서 위치 1의 글자가 추가되었다고 가정한 상태( Øs (= Øss) )에서 교체(Øss -> Øsa 편집거리 1 추가)되는 것이다.

Ø -> Øs (= Øss) -> Øsa

2번 변했으니 편집거리는 2

 

3) 알파벳을 삭제하는 경우

이 경우는 original이 Ø -> s -> sa 된 상태(현재 편집거리가 2)에서 아래로 내려가는 것이므로 s가 추가되었다고 가정한 상태에서 문제 하나를 삭제하는 것이다.

Ø -> Øs -> Øsa (= Øsas) -> Øsa

3번 변했으니 편집거리는 3

 

 

 

 

정답코드

---

original_string = list(input())
new_string = list(input())

row_length = len(original_string)+1
col_length = len(new_string)+1

dp = [[5000] * (col_length) for _ in range(row_length)]


dp[0][0] = 0
for i in range(1, col_length):
    dp[0][i] = i

for i in range(1, row_length):
    dp[i][0] = i

for i in range(1, row_length): # i : ori
    for j in range(1, col_length): # j : new
        if original_string[i-1] == new_string[j-1]:
            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

print(dp[row_length-1][col_length-1])

 

 

 

 

 

 

 

 

느낀점

---

dp문제는 거의 혼자 풀 수 없던 문제가 많았다.

게다가 이 문제는 답을 보고도 해결까지 2~3시간이 걸리고, 블로그에 풀이법을 정리하는데에도 4시간이 걸렸다.

 

왼쪽에서 오른쪽으로 가는것이 삽입

대각선으로 가는 것이 교체

아래로 가는 것이 삭제

이 세개를 이해하는데에 시간이 오래걸렸다.

답을 보고도 이해를 못하는데 문제를 풀때 풀이과정을 어떻게 떠올릴까..

 

풀이법도 이해되기 쉽게 설명하는 것도 어려웠다.

 

이런문제들은 잘풀려면 많이푸는 방법밖에 없을까?.....

알고리즘 기법들 복습하고 dp문제를 죽도록 풀어봐야겠다..