검색결과 리스트
dynamic programming에 해당되는 글 7건
- 2012.08.09 Dynamic Programming - Edit Distance, Two-Person Traversal...
- 2012.08.07 Dynamic Programming - Counting Boolean Parenthesizations, Optimal Strategy for a Game
- 2012.08.06 Dynamic Programming - Building Bridges, Balanced Partition. 2
- 2012.08.03 Dynamic Programming - Longest Increasing Subsequence, Box Stacking
- 2012.08.01 Dynamic Programming - Make Change Problem 2
- 2012.07.31 Dynamic Programming - Maximal Contiguous Subsequent Sum Problem 2
- 2012.07.31 Dynamic Programming - Knapsack Problem
글
Dynamic Programming - Edit Distance, Two-Person Traversal...
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 이란 사람의 리플을 보고 풀었다.
'프로그래밍' 카테고리의 다른 글
글
Dynamic Programming - Counting Boolean Parenthesizations, Optimal Strategy for a Game
- 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는 당췌 아이디어가 안 떠오르네...
'프로그래밍' 카테고리의 다른 글
fgets(buf, buf_size, stdin), gets(buf) 차이? (0) | 2013.02.20 |
---|---|
Dynamic Programming - Edit Distance, Two-Person Traversal... (0) | 2012.08.09 |
Dynamic Programming - Building Bridges, Balanced Partition. (2) | 2012.08.06 |
Dynamic Programming - Longest Increasing Subsequence, Box Stacking (0) | 2012.08.03 |
Dynamic Programming - Make Change Problem (2) | 2012.08.01 |
글
Dynamic Programming - Building Bridges, Balanced Partition.
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 를 기준으로 좌/우로 나누는 건줄 알았다.
그래서 문제를 이해해서 제대로 못 풀었다.
그리고 해답을 얼핏 보고 아하.. 하고 다시 푼 문제.
'프로그래밍' 카테고리의 다른 글
Dynamic Programming - Edit Distance, Two-Person Traversal... (0) | 2012.08.09 |
---|---|
Dynamic Programming - Counting Boolean Parenthesizations, Optimal Strategy for a Game (0) | 2012.08.07 |
Dynamic Programming - Longest Increasing Subsequence, Box Stacking (0) | 2012.08.03 |
Dynamic Programming - Make Change Problem (2) | 2012.08.01 |
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem (2) | 2012.07.31 |
글
Dynamic Programming - Longest Increasing Subsequence, Box Stacking
- 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 처럼 크다, 작다, 크지도 작지도 않다, 같다.. 이런식으로 구분되는 것에는 좀 주의해야 하겠다.
'프로그래밍' 카테고리의 다른 글
Dynamic Programming - Counting Boolean Parenthesizations, Optimal Strategy for a Game (0) | 2012.08.07 |
---|---|
Dynamic Programming - Building Bridges, Balanced Partition. (2) | 2012.08.06 |
Dynamic Programming - Make Change Problem (2) | 2012.08.01 |
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem (2) | 2012.07.31 |
Dynamic Programming - Knapsack Problem (0) | 2012.07.31 |
글
Dynamic Programming - Make Change Problem
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 )
이 문제는 약간 어려웠던거 같다. 그냥 생각만으로는 잘 안되서,
아주 간단한 케이스를 가지고 종이에 적어가면서 확인했다.
조합의 수를 구하는 문제는 좀 헷갈리긴 했지만,
생각을 좀 해보고, 간단한 케이스를 확인해 보면서 찾을 수 있었다.
'프로그래밍' 카테고리의 다른 글
Dynamic Programming - Building Bridges, Balanced Partition. (2) | 2012.08.06 |
---|---|
Dynamic Programming - Longest Increasing Subsequence, Box Stacking (0) | 2012.08.03 |
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem (2) | 2012.07.31 |
Dynamic Programming - Knapsack Problem (0) | 2012.07.31 |
Eclipse CDT + Cygwin 으로 C/C++ 개발 환경 설정 관련... (0) | 2012.06.29 |
글
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem
문제) N 개의 실수 A(1) ~ A(N)이 있을 때, 연속된 수 A(i) ... A(j)의 합이 최대가 되는 값을 구하라.
솔직히 Brute Force 방식으로 풀어도 O(N^3)의 복잡도를 가지므로,
NP-Complete 한 문제는 아니다.
하지만 D.P 연습으로 공부를 하는 거니깐.
D.P 문제 중에는 난이도가 낮은 문제가 아닐까?
'프로그래밍' 카테고리의 다른 글
Dynamic Programming - Building Bridges, Balanced Partition. (2) | 2012.08.06 |
---|---|
Dynamic Programming - Longest Increasing Subsequence, Box Stacking (0) | 2012.08.03 |
Dynamic Programming - Make Change Problem (2) | 2012.08.01 |
Dynamic Programming - Knapsack Problem (0) | 2012.07.31 |
Eclipse CDT + Cygwin 으로 C/C++ 개발 환경 설정 관련... (0) | 2012.06.29 |
글
Dynamic Programming - Knapsack Problem
- Knapsack Problem
Dynamic Programming을 공부하면서,
(정말 정말 너무나 쉬운) Fibonacci 수열의 값을 구하는 예를 제외하고,
가장 많이 이용되는 예가 아닐까?
열 마디 설명보다 그림이 이해하기 쉬우므로, 부담없이 인용할 수 있는 위키피디아 그림을 가져왔다.
|
위 그림과 같이 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 한 방법을 통해 해결할 수 있다.
'프로그래밍' 카테고리의 다른 글
Dynamic Programming - Building Bridges, Balanced Partition. (2) | 2012.08.06 |
---|---|
Dynamic Programming - Longest Increasing Subsequence, Box Stacking (0) | 2012.08.03 |
Dynamic Programming - Make Change Problem (2) | 2012.08.01 |
Dynamic Programming - Maximal Contiguous Subsequent Sum Problem (2) | 2012.07.31 |
Eclipse CDT + Cygwin 으로 C/C++ 개발 환경 설정 관련... (0) | 2012.06.29 |