티스토리 뷰
반응형
문제보러가기
https://www.acmicpc.net/problem/15483
문제 정의
문자열 A와 B가 있다.
A를 어떠한 동작을 통해 B와 같게 만들려고 한다.
이 때 최소한의 동작 횟수를 구하시오.
각 순간마다 세가지의 선택을 할 수 있다.
- 1 삽입
- 2 삭제
- 3 교체
이 문제를 어떻게 해결할 수 있을까?
이 문제의 접근법은 모든 가능성을 탐색하는 것이다.
재귀를 이용하여 두 문자열의 다름 정도의 비교를 할 수 있다.
String S1 의 i 인덱스, S2 의 j 인덱스를 다름을 비교하여,
만약 같다면 다음 비교 스테이지인 S1의 i+1, S2의 j+1로 넘어간다.
만약 다르다면, S1에게 3가지 동작을 수행할 수 있다.
삭제, 더하기, 교체 이다.
만약 삭제하는 경우 다음 비교 스테이지인 S1의 i+1, S2의 j로 넘어간다.
만약 더하기인 경우 다음 비교 스테이지인 S1의 i, S2의 j+1로 넘어간다.
만약 교체인 경우 다음 비교 스테이지인 S1의 i+1, S2의 j+1로 넘어간다.
각 세가지 동작의 비용은 1인 것을 유의하자.
string f, t; int go(int i, int j) { if ( f.size() == i && t.size() == j ) return 0; if ( f.size() == i || t.size() == j) { if ( f.size() == i ) return t.size() - j; else return f.size() -i; } int mn = 1e9; // MAX; if ( f[i] == t[j] ) return go(i+1, j+1); else { mn = min( mn , go(i+1, j) +1 ); // erease mn = min( mn , go(i, j+1) +1 ); // add mn = min( mn , go(i+1, j+1) +1); // replace } return mn; }
여기서 중복되는 경우의 수가 있으니, memoization을 하면 되겠다.
정답 소스 보러가기
https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/15483.cc
문제에 대해 이야기해보다
연습대회에 나왔는데 풀지 못했다. 일주일이 지난 뒤에야 정리하게 되었다....
문제를 보았을 때
완전탐색이었을 것 같았지만 경우의 수만 세어보고 불가능하다고 판단하였다. 만약 재귀문으로 작성하려 시도하였으면, 충분히 풀었을 것 같다.
대부분의 시간을 LIS류의 패턴매칭하는 부분 문제일 것이라 생각하고 그 것을 활용한 해결법에 몰두 하고 있었다.
소스로는 간단하게 작성하고 해결할 수 있는 문제였는데...
무엇보다도 문제 해결에 있어 재귀적 접근에 대해 스스로가 인색한 것 같다.
문제를 잘 정의하고, 주의해보자...
반응형
'알고리즘 문제 > DP' 카테고리의 다른 글
백준 14494 다이나믹이 뭐에요? (0) | 2019.09.17 |
---|---|
백준 1463 1로 만들기 (0) | 2019.09.17 |
백준 15991 1, 2, 3 더하기 - 6 (0) | 2018.10.23 |
백준1126 같은탑 (0) | 2017.12.05 |
BOJ 1520 : 내리막길 (0) | 2017.11.11 |
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 데이터 중심 애플리케이션 설계
- 이산수학
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- Arena
- 그라파나
- Propositional and Predicate Logic
- 아레나시뮬레이션
- 대규모 시스템 설계 기초
- 아레나
- Discrete Mathematics
- 자바스크립트
- arena simulation
- 최단경로 알고리즘
- 아레나 시뮬레이션
- beginning javascript
- 로젠
- javascript
- flutter
- rosen
- 이산 수학
- paul wilton
- 명제논리
- 백준
- Simulation
- 시뮬레이션
- 자바스크립트 예제
- 조합 코딩
- Trie
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- grafana cloud
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 29 | 30 |
글 보관함