문제 : 편집 거리
풀이
해결에 필요한 핵심 아이디어: 리벤 슈타인(편집 거리) 알고리즘
리벤 슈타인 알고리즘?
•
두 문자열 A, B가 얼마나 유사한지 알아낼 수 있는 알고리즘
→ 문자열 A가 문자열 B가 되기 위해서 필요한 최소 연산횟수는 얼마인가
•
여기서 연산이란?
1.
삽입 : 문자열 A의 한 위치에 문자 하나를 삽입
2.
삭제 : 문자열 A의 문자 하나를 삭제
3.
교체 : 문자열 A의 문자 하나를 다른 문자로 교체
•
예시 : abcd vs bcde
{ } | b | c | d | e | |
{ } | 0 | 1 | 2 | 3 | 4 |
a | 1 | 1 | 2 | 3 | 4 |
b | 2 | 1 | 2 | 3 | 4 |
c | 3 | 2 | 1 | 2 | 3 |
d | 4 | 3 | 2 | 1 | 2 |
1.
2차원 테이블 생성
•
행은 문자열 A의 각각의 문자로, 열은 문자열 B의 각각의 문자로 간주
◦
행과 열의 첫번째 요소는 공백으로 한다.
•
테이블에 저장될 숫자는 다음을 의미
◦
문자열 A의 해당 행까지의 부분 문자열로
문자열 B의 해당 열까지의 부분 문자열을 만드는 데 필요한 최소 연산횟수
2.
첫 번째 행의 열, 첫 번째 열의 행 요소들은 모두 각각 열과 행의 인덱스로 초기화
•
ex : 첫 번째 행({ })의 요소들
◦
{ } → { } 최소 연산횟수 : 0
◦
{ } → b 최소 연산횟수 : 1
◦
{ } → c 최소 연산횟수 : 2
◦
{ } → d 최소 연산횟수 : 3
◦
{ } → e 최소 연산횟수 : 4
3.
테이블의 나머지 요소들은 다음 규칙을 따르며 초기화시켜주면 됨.
•
A[i - 1] == B[j - 1]
◦
DP[i][j] = DP[i - 1][j - 1]
◦
abc → bc에서 c는 같으므로 ab → b 편집 거리를 그대로 가져오면 됨.
•
A[i - 1] != B[j - 1]
◦
DP[i][j] = min(DP[i - 1][j - 1], DP[i - 1][j], DP[i][j - 1]) + 1
▪
DP[i - 1][j - 1] + 1 → 교체를 할 경우
•
ab → bcd에서 b를 d로 교체하면, a → bc 편집 거리 사용 가능
▪
DP[i - 1][j] + 1 → 삭제를 할 경우
•
ab → bcd에서 b를 삭제하면, a → bcd 편집 거리 사용 가능
▪
DP[i][j - 1] + 1 → 삽입을 할 경우
•
ab → bcd에서 d를 삽입하면, ab → bc 편집 거리 사용 가능
→ 위 세 경우 중 최솟값을 저장시켜주면 된다!
풀이
