파비의 매일매일 공부기록

DP 정복 - 5.1 최소 교정 비용 문제 본문

Study/Algorithm 문제풀이

DP 정복 - 5.1 최소 교정 비용 문제

fabichoi 2021. 9. 1. 23:30

5장은 문제를 풀어보면서 이전 장들에서 설명한 이론들을 적용해본다.

그래서 이번 장은 문제당 포스팅 한 개를 쓰기로 했다.

 

오늘은 '최소 교정 비용 문제'인데

어디서 많이 본 듯한 유형이긴 한데.. BOJ에 없어서 제출해보는 건 패스 ㅠㅠ

 

입력은 두 개의 문자열이다.

두 문자열이 수행할 수 있는 연산은

1. 삽입

2. 삭제

3. 치환

이다. 세 가지 연산을 이용해 두 개의 문자열을 동일하게 만들 때 발생하는 최소 비용을 구하는 게 문제다.

 

재귀로 풀 경우 다음의 조건을 적용하면 된다.

 

1. 두 글자가 같으면 두 단어의 첫 번째 글자에 대해서는 아무런 조치를 할 필요가 없다. 또한 첫 번째 글자를 제외하고 다음 글자로 넘어가서 최소 교정 비용을 찾으면 된다. 다시 말해 그냥 '무시' 하면 된다.

 

2. 두 글자가 다르면

 2-1. 삭제 : 첫 번째 단어의 첫 번째 글자를 삭제하고 두 번째 단어와 비교.

 2-2. 치환 : 첫 번째 단어의 첫 번째 글자를 두 번째 단어의 첫 번째 글자로 치환한 뒤, 두 단어의 첫 번째 글자를 제외한 단어 간의 최소 교정 비용을 구함. 

 2-3. 삽입 : 두 번째 단어의 첫 번째 글자를 첫 번째 단어의 제일 앞에 삽입하고, 두 단어의 첫 번째 글자를 제외한 나머지 글자에 대한 최소 교정 비용을 구함. 첫 번째 단어의 길이는 1 증가.

 

위의 조건을 기반으로 구현한 코드는 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve(s1, s2):
    if len(s1) == 0:
        return len(s2)
    if len(s2) == 0:
        return len(s1)

    if s1[0] == s2[0]:
        return solve(s1[1:], s2[1:])

    d = solve(s1[1:], s2)
    u = solve(s1[1:], s2[1:])
    i = solve(s1, s2[1:])

    return min(d, u, i) + 1


if __name__ == '__main__':
    print(solve(input(), input()))

위의 코드는 실제로는 못쓴다고 봐야 된다.

시간 복잡도가 O(3^n)이기 때문에 n이 늘어날수록 시간이 기하급수적으로 늘어나기 때문.

 

그래서 DP로 풀어보는 방식을 소개한다.

첫 번째 단어의 길이를 n, 두 번째 단어의 길이를 m으로 놓는다면

전체 조합의 개수는 (m+1) * (n+1) 개가 된다. (빈 문자열인 경우 포함)

 

표로 나타낸 건 책으로 나와 있다. 로직을 풀어쓰면,

1. 두 글자가 같으면 교정 비용의 차이가 없어 대각선 방향 왼쪽 위 셀을 값을 가져옴.

2. 두 글자가 다르면 위쪽, 왼쪽, 왼쪽 위 셀의 최솟값을 가져와서 1을 더함. 이전의 재귀에서 삽입/삭제/치환 연산을 한 것 과 동일하다고 보면 됨.

 

마지막으로 배열의 m, n의 값을 리턴해주면 된다.

코드로 나타내면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)

def solve_dp(s1, s2):
    m, n = len(s1) + 1, len(s2) + 1
    ar = [[0 for _ in range(m)] for __ in range(n)]

    for i in range(n):
        ar[i][0] = i
    for i in range(m):
        ar[0][i] = i

    for i in range(1, m):
        for j in range(1, n):
            if s1[j - 1] == s2[i - 1]:
                ar[i][j] = ar[i - 1][j - 1]
            else:
                ar[i][j] = min(ar[i][j - 1], ar[i - 1][j], ar[i - 1][j - 1]) + 1

    return ar[n - 1][m - 1]


if __name__ == '__main__':
    print(solve_dp(input(), input()))

이 문제에서 재귀를 DP로 바꾸는 데 사용된 아이디어는

3개의 CASE에 대해 2차원 배열로 변환하고

왼쪽, 위쪽, 대각선 왼쪽 위를 활용하는 것이다.

 

아무것도 없는 상황에서 이런 내용을 생각할 수 있을까...

 

아직도 멀긴 먼 듯싶다 ㅎㅎㅎㅎㅎ

반응형
Comments