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








반응형

설정

트랙백

댓글

- Counting Boolean Parenthesizations

문제) 5개의 심볼을 가지고 만든 Boolean Expression을 괄호로 묶어 Evaluation했을 때,

        결과가 true 가 되는 Case 의 갯수는 몇 개인가?

        심볼 = { true, false, and, or, xor }

        예를 들면, ' false and true xor true '가 true 가 되는 괄호 묶기 방법은 1가지 밖에 없다.




- Optimal Strategy for a Game

문제) N 개의 동전이 있다. (N은 항상 짝수)

        각 동전의 가치는 V(0)...V(N)이며, 이 동전들은 일렬로 놓여져 있다.

        두 사람이 일렬로 놓여져 있는 동전의 양쪽 끝 동전 중 하나를 가질 수 있다고 할 때,

        처음 시작하는 사람이 가능한 최대 금액은 얼마인가?


       상대방이 무엇을 선택하는지는 여기에서 문제가 아니다.

       모든 경우의 수에서 최대값을 찾는 문제인 것이다.

       처음엔 "상대방은?" 이라는 생각에 잠시 혼란스러웠었다.



두 문제 다, 나름 풀만한 문제였다.

근데, 이 두 문제 전에 있는 문제인 Edit Distance는 당췌 아이디어가 안 떠오르네...








반응형

설정

트랙백

댓글

1) Building Bridges

문제내용:

가운데로 강이 지나가는 2차원 지도가 있다. 강 북쪽과 남쪽으로 각각 N 개의 도시가 있다.

이 N 개의 도시를 A(1)...A(N), B(1)...B(N) 이라고 한다.

이 도시는 순서대로 위치해 있지는 않다. (즉 A(1) 옆에 A(2) 가 있는게 아니라는 말)

강 북쪽과 남쪽은 연결하는 다리를 건설하고자 하는데,

다리의 건설은 A(k) 와 B(k) 만 연결할 수 있다.

이 때, 가장 다리를 많이 놓을 수 있는 갯수는 몇 개 인가?


설명이 은근히 길다.

그림으로 그리고 싶지만, 잘 찾지도 못하겠고 그리기도 귀찮아서 패스.





- Balanced Partition

문제:

N 개의 정수를 가진 집합을 2개의 Subset S1, S2 로 나누었을 때, |Sum(S1) - Sum(S2)| 의 최소값을 구하라.


사실 이 문제는 내가 못 풀었다.

Subset 을 나누는 데, 단순히 한 Element 를 기준으로 좌/우로 나누는 건줄 알았다.

그래서 문제를 이해해서 제대로 못 풀었다.

그리고 해답을 얼핏 보고 아하.. 하고 다시 푼 문제.





반응형

설정

트랙백

댓글

  • 익명 2015.11.13 19:26 답글 | 수정/삭제 | ADDR

    비밀댓글입니다

    • BlogIcon 아자 2015.11.26 11:28 신고 수정/삭제

      안녕하세요? 블로그 글 내에 소스코드가 포함되어 있습니다.

- Longest Increasing Subsequence

임의의 순서로 나열된 집합 A 가 있을 때,

값이 증가하는 최장 길이 수열을 찾는 문제이다.

단, 수열은 인접해 있을 필요는 없고,

이러한 수열은 여러가지 종류가 있을 수 있다.


예를들어 아래와 같은 수열이 있을 경우

{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }

LIS 는 0, 2, 6, 9, 13, 15 혹은 0, 4, 6, 9, 11, 15 이 되겠다.


처음에는 2차원 배열로 계산을 했었는데,

그다지 좋은 방법은 아니었다. 

메모리도 많이 쓰고 최장 길이는 찾을 수 있었으나, 실제 수열을 찾지는 못했기에...




- Box Stacking

임의의 N 개 타입의 박스가 있을 때, 박스를 가장 높이 쌓을 수 있는 경우와 그 높이를 구하는 문제이다.

박스의 갯수는 제한이 없다. 

단, 박스를 쌓기 위해서는 strictly larger 야 한다.

( 즉, 박스의 Width > Depth 라고 했을 때,

 아래박스.Width > 위박스.Width && 아래박스.Depth > 위박스.Depth 를 만족해야 한다. )



* Box Stacking 문제부터 STL을 사용 해 보았는데,

  Box Class 의 Sorting 이 조금 문제가 있었다.

  STL 의 sort() 를 이용하기 위해 operator < 오버로딩 하였는데,

  단순히 return (w > b.w && d > d.w); 를 하게 되면,

  원하는대로 정렬이 되지 않아, !((w < b.w) || (d < b.d)); 를 사용하였다.

  Box 처럼 크다, 작다, 크지도 작지도 않다, 같다..  이런식으로 구분되는 것에는 좀 주의해야 하겠다.





반응형

설정

트랙백

댓글

N 개 타입의 동전으로 어떠한 금액을 만드는 것과 관련된 문제이다.


여기서 몇 가지 문제를 생각할 수 있는데,


1. Frobenius coin problem

이 문제는 NP-hard 문제로, GCD(최대공약수)가 1인 N 개 타입의 동전으로 만들 수 없는,

가장 큰 수를 찾는 문제이다. 이 수를 Frobenius(프로베니우스) number 라 한다.

하지만 N이 1,2,3 일 때는 다항시간에 찾을 수 있는 공식이 나와있다.

더 자세

한 내용은 위키피디아 http://en.wikipedia.org/wiki/Coin_problem 참고.



2. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가장 적은 수의 동전을 사용했을 때의 동전의 수.

(단 N >= 1 이고 N[1] = 1 )

요 문제는 Greedy 한 방법으로 풀어도 되지만, DP 방법으로 풀 수도 있다.




3. N 개 타입의 동전으로 어떠한 금액을 만들 때, 가능한 동전 조합의 경우의 수를 구하는 경우.

(단 N >= 1 이고 N[1] = 1 )

이 문제는 약간 어려웠던거 같다. 그냥 생각만으로는 잘 안되서,

아주 간단한 케이스를 가지고 종이에 적어가면서 확인했다.




조합의 수를 구하는 문제는 좀 헷갈리긴 했지만,

생각을 좀 해보고, 간단한 케이스를 확인해 보면서 찾을 수 있었다.

반응형

설정

트랙백

댓글

  • 익명 2015.03.19 02:15 답글 | 수정/삭제 | ADDR

    비밀댓글입니다

    • BlogIcon 아자 2015.03.31 13:11 신고 수정/삭제

      앗.. 그렇군요.. 지적 감사합니다.
      내용 수정하겠습니다.

문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.


솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,

NP-Complete 한 문제는 아니다.

하지만 D.P 연습으로 공부를 하는 거니깐.



D.P 문제 중에는 난이도가 낮은 문제가 아닐까?

반응형

설정

트랙백

댓글

  • MaxSum 2012.08.29 10:42 답글 | 수정/삭제 | ADDR

    You can calculate the sum in O(n) using Kadane's Algorithm.

    int a[n]; // randomized numbers

    int t = 0;
    int s = INT_MIN;
    int k = 0; l = 0;
    int j = 0;
    for(int i = 0; i < n; i++){
    t = t + a[i];
    if( t > s ){
    s = t;
    k = j; l = i;
    }
    if( t < 0 ){
    t = 0;
    j = i + 1;
    }
    }

    then s is max sum from k to l on 1D array

    • BlogIcon 아자 2012.08.30 10:07 신고 수정/삭제

      Wow, Thanks.
      I didn't know that algorithm.
      I'll modify my article.

- Knapsack Problem

Dynamic Programming을 공부하면서,

(정말 정말 너무나 쉬운) Fibonacci 수열의 값을 구하는 예를 제외하고,

가장 많이 이용되는 예가 아닐까?


열 마디 설명보다 그림이 이해하기 쉬우므로, 부담없이 인용할 수 있는 위키피디아 그림을 가져왔다.

File:Knapsack.svg
(저자: Dake, 출처: http://en.wikipedia.org/wiki/File:Knapsack.svg )


위 그림과 같이 15kg까지 담을 수 있는 배낭에

각각 Value와 Weight를 가진 N 종류 타입의 상자들을 담았을 때,

Max Value가 되는 값이 얼마인가? 를 구하는 문제이다.


Knapsack Problem에는 3가지 종류가 있다.

이 구분은 사용가능한 N 종류 타입의 아이템의 갯수에 따라 나뉜다.

(위 그림으로 치자면 상자의 각 타입의 상자가 몇 개씩 있느냐?)


1. 0-1 Knapsack Problem : N 개의 타입의 아이템이 1개씩 있음.

2. Bounded Knapsack Problem : N 개의 타입의 아이템이 x(임의의 갯수)개씩 있음.

3. Unbounded Knapsack Problem : N 개의 타입의 아이템의 갯수 제한이 없음.


기본적인 해결 아이디어는 동일하다.

하지만 종류에 따라 아이디어를 조금 간소화 시킬 수 있다.


3가지 방법에 대해 일반적으로 사용할 수 있는 Knapsack 소스는 다음과 같다.



결론

다시 한번봐도 어렵긴 마찬가지다.

여러가지 D.P 문제들을 보고 익숙해지길 바라는 수 밖에.



(추가사항)

Knapsack Problem 중에 아이템을 쪼갤수 있는 Case의 경우는,

Value/Weight 가 높은 순으로 Greedy 한 방법을 통해 해결할 수 있다.

반응형

설정

트랙백

댓글