Q36. 편집 거리
🐣문제
두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.
1. 삽입 (insert) : 특정한 위치에 하나의 문자를 삽입합니다.
2. 삭제 (delete) : 특정한 위치에 있는 하나의 문자를 삭제합니다.
3. 교체 (replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.
이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3 입니다.
🐥풀이
dp 테이블은 어떻게 초기화 해야할까?
문자열을 비교하여, 거리 기준으로 dp 테이블이 이루어진다. 예를들어,
∅ s a t u r d a y ∅ 0 1 2 3 4 5 6 7 8 s 1 0 0 0 0 0 0 0 0 u 2 0 0 0 0 0 0 0 0 n 3 0 0 0 0 0 0 0 0 d 4 0 0 0 0 0 0 0 0 a 5 0 0 0 0 0 0 0 0 y 6 0 0 0 0 0 0 0 0 다음과 같은 표를 보자. ∅은 빈 문자열이라는 뜻이다. 그럼 초기에 가로의 0~8과 세로의 0~6은 무엇일까? 빈문자열과 문자열 사이의 거리이다. dp[0][5]는 빈문자열과 'satur' 사이의 거리라는 뜻인데, 당연히 satur은 5글자고 빈문자열과 비교하면 거리는 5가 된다. 이런 원리로 dp 테이블을 업데이트 해나간다.
점화식은 어떻게 세워야할까?
dp를 어떤 원리로 이루어져 있는 지는 알았는데, 어떻게 채워나가야할까? 거리 사이를 어떻게 구할 지를 모르겠다😭 다음을 보자.
∅ s a t ∅ 0 1 2 3 s 1 1 2 3 u 2 2 3 ? 어떠어떠한 원리로 dp 테이블을 채워왔다고 하자. 그럼 이제 dp[2][3] 칸을 채워야 한다. dp[2][3]은 문자열 "sat"과 문자열 "su"의 편집 거리를 채워넣는 곳이 된다. 거리를 어떻게 구할까..?
결론부터 말하면, 위쪽(삭제), 왼쪽 위(교체), 왼쪽(삽입) 중 최솟값을 구해서 1을 더한다. (새로운 연산)
정말.. 왜 위쪽이 삭제며,, 왼쪽 위가 교체며,, 왼쪽이 삽입인지.. 도통 이해가 안됐었다. 😒
나름 구글링해가며 내린 결론은 다음과 같다..! (정확하지 않으니 100% 신뢰 NOooo...)
우선, dp에서는 위쪽 문자열(sat)을 기준으로 왼쪽 문자열(su)을 편집하는 것으로 보자.
(삭제, delete, 위) 위쪽으로 옮기면, 위쪽 문자열(sat)은 그대로! 왼쪽 문자열(su)은 s로 문자열 하나가 없어지는 자리로 돌아온다ㅇㅁㅇ!! 그래서 삭제!
(교체, replace, 왼쪽 위) 왼쪽 위로 옮기면, 위쪽 문자열(sat)도, 왼쪽 문자열(su)도 각각 하나씩 줄어 "sa"와 "s"인 자리로 돌아온다. 같은 연산이네? 교체!!
(삽입, insert, 왼쪽) 왼쪽으로 옮기면, 위쪽 문자열(sat)은 sa로 문자열 삭제, 왼쪽 문자열(su)은 그대로인 자리로 돌아온다. 왼쪽 문자열을 편집하는 기준으로 봤고, 위쪽 문자열의 문자 하나가 빠졌으니 삽입!!
그럼 효율적인 전 연산 결과의 값은 min으로 들고 왔다. 여기에 새로운 연산이 더해지므로 +1 해준다.
따라서 점화식은 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1 이 된다.
당연히 두 문자열의 최소 편집 거리는 마지막 자리인 dp[n-1][m-1]로 출력하면 된다.
🐓코드
# 입력값
str1 = input()
str2 = input()
# dp 테이블 초기화
dp = [[0]*(len(str1)+1) for _ in range(len(str2)+1)]
for i in range(1,len(str1)+1): dp[0][i] = i
for i in range(1,len(str2)+1): dp[i][0] = i
for i in range(1,len(str2)+1):
for j in range(1,len(str1)+1):
if str1[j-1]!=str2[i-1]:
# 위(삭제), 왼쪽 위(교체), 왼(삽입)
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
# 문자열 같으면 연산 X
else:
dp[i][j] = dp[i-1][j-1]
print(dp[len(str2)][len(str1)])⭐2022.05.10
무지막지 어려웠음 ㅠㅠ 스터디 당시에는 그냥 삽입, 교체, 삭제 자리를 외워가지고 풀었는데 조금 그 때보다 이해가 더 된 느낌이 들어 뿌듯하다 ㅎㅎㅎㅎ
