일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 영어원서읽기
- 화상영어
- FIT XR
- 잡생각
- 리얼 클래스
- 프로젝트
- 매일
- Writing
- 운동
- 뭐든
- 괜찮음
- 영어공부
- 미드시청
- 30분
- 10분
- 만화도
- 사이드
- Daily Challenge
- 스탭퍼
- 3줄정리
- realclass
- leetcode
- 링피트
- 개발자
- 읽기
- 쓰릴오브파이트
- 월간
- English
- Problem Solving
- 파비최
- Today
- Total
파비의 매일매일 공부기록
DP 정복 - 5.1 최소 교정 비용 문제 본문
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차원 배열로 변환하고
왼쪽, 위쪽, 대각선 왼쪽 위를 활용하는 것이다.
아무것도 없는 상황에서 이런 내용을 생각할 수 있을까...
아직도 멀긴 먼 듯싶다 ㅎㅎㅎㅎㅎ
'Study > Algorithm 문제풀이' 카테고리의 다른 글
DP 정복 - 5.3 문자열 인터리빙 확인 문제 (0) | 2021.09.08 |
---|---|
DP 정복 - 5.2 직사각형에서 총 경로 수 구하기 (0) | 2021.09.07 |
DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결 : 예제 풀기 3 (0) | 2021.08.31 |
DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결 : 예제 풀기 2 (0) | 2021.08.30 |
DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결 : 예제 풀기 1 (0) | 2021.08.29 |