- 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차원 배열로 계산을 했었는데,
그다지 좋은 방법은 아니었다.
메모리도 많이 쓰고 최장 길이는 찾을 수 있었으나, 실제 수열을 찾지는 못했기에...
최장 길이와 수열을 모두 구하는 아이디어는 다음과 같다.
A[] - 집합 A
DP[j] : 0 ~ j th 까지의 LIS 값.
DP[j] 는 A[0] ~ A[j-1] 중 A[j] 보다 작으면서,
DP[] 값이 가장 긴 원소를 찾아 연결하면 된다.
점화식은 아래와 같다.DP[j] : 0 ~ j th 까지의 LIS 값.DP[0] = 1
DP[j] = MAX(DP[k] + 1) // 단 k = 0 ... j-1, A[j] > A[k] 인 경우
P[j] : j th Element 가 속한 LIS 에서 이전 Element 를 가리키는 Index
위와 같은 아이디어로 풀면 O(n^2) 복잡도가 나온다.
위키피디아에는 O(n log n) 으로 개선이 가능하다는데, 귀찮아서 패스.
void find_lis() {
int i, j, prev;
// Simple way
for(i = 0; i < NUM_OF_NUMBERS; i++) {
prev = -1;
DP[i] = 0;
DP_PREV[i] = -1;
for(j = i-1; j >= 0; j--) {
if(A[i] > A[j] && DP[j] > DP[prev])
prev = j;
}
if(prev == -1)
DP[i] = 1;
else
DP[i] = DP[prev] + 1;
DP_PREV[i] = prev;
}
}
- Box Stacking
임의의 N 개 타입의 박스가 있을 때, 박스를 가장 높이 쌓을 수 있는 경우와 그 높이를 구하는 문제이다.
박스의 갯수는 제한이 없다.
단, 박스를 쌓기 위해서는 strictly larger 야 한다.
( 즉, 박스의 Width > Depth 라고 했을 때,
아래박스.Width > 위박스.Width && 아래박스.Depth > 위박스.Depth 를 만족해야 한다. )
아이디어는 다음과 같다.
1. Box 타입을 재구성.
Box 는 Rotation 이 가능하므로,
Box 의 H, W, D 가 각각 H 가 되는 경우로 나눔. 단, 재구성한 타입에서는 W > D 가 되도록 함.
2. 재구성한 Box 타입을 Sort. (큰 박스가 먼저 오도록.)
3. 위의 LIS 아이디어를 적용하여 문제 해결.
void box_stacking() {
int i, j, total_max, max_height;
DP[0] = B2[0].h;
PREV[0] = -1;
total_max = 0;
for(i = 1; i < (int)B2.size(); i++) {
DP[i] = B2[i].h;
PREV[i] = -1;
max_height = 0;
for(j = 0; j < i; j++) {
if(B2[j].canStack(B2[i]) && DP[j] > max_height) {
DP[i] = DP[j] + B2[i].h;
PREV[i] = j;
max_height = DP[j];
}
}
if(DP[i] > total_max)
total_max = DP[i];
}
}
* Box Stacking 문제부터 STL을 사용 해 보았는데,
Box Class 의 Sorting 이 조금 문제가 있었다.
STL 의 sort() 를 이용하기 위해 operator < 오버로딩 하였는데,
단순히 return (w > b.w && d > d.w); 를 하게 되면,
원하는대로 정렬이 되지 않아, !((w < b.w) || (d < b.d)); 를 사용하였다.
Box 처럼 크다, 작다, 크지도 작지도 않다, 같다.. 이런식으로 구분되는 것에는 좀 주의해야 하겠다.