검색결과 리스트
Box Stacking에 해당되는 글 1건
글
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 |
