Search

편집 거리

문제 : 편집 거리

풀이

해결에 필요한 핵심 아이디어: 리벤 슈타인(편집 거리) 알고리즘

리벤 슈타인 알고리즘?

두 문자열 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 편집 거리 사용 가능
→ 위 세 경우 중 최솟값을 저장시켜주면 된다!
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.