http://people.csail.mit.edu/bdean/6.046/dp/

위 링크의 Dynamic Programming 문제들 중,

남은 두 문제인 Edit Distance 와 Two-Person Traversal of a Sequence of Cities 에 대하여 정리해 본다.

( 12번 Bin Packing 은 굳이 할 필요가 없어 패스 )

이 두 문제는 도대체 해결방법이 떠오르지 않아, 인터넷의 풀이를 보고 말았다.

두 문제의 풀이를 보면서 일단 DP 문제라도,

문제를 Recursive 하는 푸는 방법을 떠 올리고,

거기서 DP 풀이를 찾는 것이 좋겠다는 생각이 들었다.



- Edit Distance

문제) String A, String B 가 있을 때, A -> B 로 바꾸는 최소한의 Operation 수를 구하는 문제이다.

        Operation 은 다음과 같은 3 가지가 있다.

        1. Insert a character, 2. Remove a character, 3. Change a character to another character.


이 문제는 아래 링크의 풀이를 참고하였다.

https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/styles/pages/editdistance.html

거기서 사용된  예를 가지고 문제를 쪼개는 방법을 설명해 본다.




- Two-Person Traversal of a Sequence of Cities

문제) 순서가 있는 N 개의 도시가 있다. (지리적으로 순서가 있다는 의미가 아니다. 방문할 수 있는 순서를 말한다. )

        그리고 각각의 도시는 모두 연결되어 있다.

        이 도시들을 두 집합으로 나누고 (연속된 도시일 필요는 없다.),

        두 사람 A, B 가 각각의 도시 집합을 방문한다고 할 때,

        A, B 의 이동거리의 합이 가장 짧은 경우는 얼마가 되는가?

        단, A, B 방문 시작점은 각 도시 집합의 첫 번째 도시이다.


처음엔 문제 자체를 이해를 못해서 한참 해멨다.

그 다음에는 문제를 어떻게 풀어야 하는지도 몰라서 한참 생각하다가,

결국 인터넷을 뒤졌는데, 이걸 깔끔하게 설명한 곳도 찾기가 힘들었다.

그리다가 아래 링크의 Grimbal 이란 사람의 리플을 보고 풀었다.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1311271494








반응형

설정

트랙백

댓글