- 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 처럼 크다, 작다, 크지도 작지도 않다, 같다..  이런식으로 구분되는 것에는 좀 주의해야 하겠다.





반응형

설정

트랙백

댓글