[백준 15483번] 최소 편집

난이도: 골드 4

15483번: 최소 편집

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

www.acmicpc.net

LCS와 유사한, 다이나믹 프로그래밍을 이용하는 문제입니다. (LCS algorithm에 대한 설명은 여기로)

두 개의 string: subject, target가 있다고 합시다. subject = 'for', target = 'whileforif' 로 하겠습니다.

subject에 적절한 연산을 통해, target과 같게 만들고자 합니다. 여기서 연산이란, 삽입, 삭제, 수정 3가지를 의미합니다.

접근 방법은 다음과 같습니다:

2-dimension array edit_distance[][]를 둡니다. 이 array는 문제를 dynamic programming 관점에서 접근하는데 사용합니다.
subject[i], target[j]를 비교하며, 같은 경우 distance의 값을 그대로 가져갑니다.
다를 경우, distance의 값을 연산량만큼 추가합니다.
subject와 target의 끝까지 위 과정을 반복한 후, 주어지는 결과를 출력합니다.

LCS의 경우와 비슷하게, 두 문자열을 각 element별로 비교하며 나타나는 결과를 표로 나타내 봅시다.

별표를 나타낸 좌표는,

fo ->while로 수정하기 위한 edit distance를 나타낸 좌표입니다. 수정 2회, 삽입 3회로 총 5회의 연산이 필요합니다.

위 표를 잘 살펴보면, 몇 가지 규칙을 찾아볼 수 있습니다.

null과 비교하는 경우, 즉 edit_distance[i][0] 또는 edit_distance [0][i]인 경우, 그 값은 지금까지 읽은 string의 길이가 된다.
subject[i]와 target[j]같은 경우, edit_distance[i][j] = edit_distance[i-1][j-1]이 된다.
같지 않은 경우, edit_distance[i][j]는 이전 좌표들의 값 중 가장 작은 값 + 1이 된다.
- 이전 좌표는 [i-1][j], [i][j-1], [i-1][j-1]을 뜻한다.

따라서 위 조건에 맞게끔 조건을 넣어 주시면 됩니다.

LCS와 조건만 조금 다르고, 굉장히 비슷한 문제 같습니다.

코드를 늘 직관적이고 읽기 쉽게 작성하려고 노력하고 있습니다.

혹시나 제 코드 중 의미 전달이 불명확한 경우가 있다면 피드백을 주시면 감사하겠습니다.

***번외***

조건이 조금 다르다면 어떻게 될까요?

위에서는 수정을 1회의 연산으로 간주했지만, 사실 수정이라 함은 삭제 후 삽입하는 것과 크게 다르지 않습니다.

바뀐 조건을 적용하여, 다시 한 번 표로 나타내 봅시다.

이번의 규칙은 어떠한가요?

null과 비교하는 경우, 즉 edit_distance[i][0] 또는 edit_distance [0][i]인 경우, 그 값은 지금까지 읽은 string의 길이가 된다.
subject[i]와 target[j]같은 경우, edit_distance[i][j] = edit_distance[i-1][j-1]이 된다.
같지 않은 경우, edit_distance[i][j]는 이전 좌표들의 값 중 가장 작은 값 + 1이 된다.
- 이전 좌표는 [i-1][j], [i][j-1]을 뜻한다.

'이전 좌표' 의 정의가 변한 것을 확인할 수 있습니다.

edit_distance array를 출력하도록 해 보았습니다.

위 표와 상황이 같나요?

subject = 'for', target = 'whilefor' 일 경우에는 앞서 언급한 케이스와 이번 케이스 모두 결과가 5로 같습니다.

이는 오직 삽입 연산만 필요로 하기 때문입니다.

subject = 'aa', target = 'bb'인 경우는 어떨까요?

앞서 언급한 케이스라면 수정을 2회, 이번 케이스라면 삭제와 삽입 각각 2회, 총 4회의 연산을 해야 할 것입니다.

결과의 차이가 보이시나요?