Algorithm Description
- Longest Increasing Subsequence는 주어진 배열 값들 중에서 증가순으로 이루어진 가장 긴 subsequence의 길이를 구하는 문제이다. 이 문제에 대한 잘 알려진 방법은 앞에서 살펴본 바와 같이 O(N2)이다. 그런데 좀 더 효율적으로 푸는 방법이 있다. 바로 지금 소개할 O(N logN) 기법이다.
- 일단 A = {2, 5, 3}을 고려해보자. (계속 확장해 나갈 것이다) LIS는 {2, 3} 또는 {2, 5} 이다. 여기에 7과 11이 새로 들어온다면 A = {2, 5, 3, 7, 11}이 되고 이 두 값들은 LIS를 단순히 확장해 나간다. 즉, LIS는 {2, 3, 7, 11} 또는 {2, 5, 7, 11} 이 된다.
- 만일 이 상황에서 8이 들어온다면 어떻게 될까? {2, 5, 3, 7, 11, 8}. 8은 현재까지의 LIS들의 (최소값이 2보다 크고) 최대값인 11보다 작기 때문에 단순히 LIS를 확장 시킬 수는 없다. 8은 LIS의 멤버가 될 수 있을까? 물론 가능성은 있다. 예를 들어, A = {2, 5, 3, 7, 11, 8, 7, 9 …} 라면 사실 8이 LIS의 멤버가 될 것이다. 따라서 8을 채택하려면 7 다음에 11을 대체하면 될 것이다. 즉, LIS는 {2, 3, 7, 8} 또는 {2, 5, 7, 8}이 된다. 사실 11보다는 8이 LIS를 확장하는데 훨씬 유리하다.
- 사실 이러한 일은 이미 {2, 5, 3} 상황에서도 있었다. 원래 LIS {2, 5} 였던 것을 3이 추가되면서 5를 대체할 수 있는 것이다.
- 그렇다면 {2, 5, 3} 상황에서 1이 추가된다면 어떻게 되나? {2, 3} 이나 {2, 5}를 확장할 수는 없다. 오히려 새로운 subsequence의 시작이 될 수 있다. 예를 들어, {2, 5, 3, 1, 2, 3, 4, 5, 6} 라고 해보자 1은 LIS의 시작이 되는 것이다.
- 위의 상황을 종합해보자. 우리는 각기 다른 길이의 active lists를 유지할 것이다. 이 리스트에 A[i]를 추가해보자. 큰 리스트부터 작은 리스트의 순서대로 검색을 하되 리스트의 마지막 원소가 A[i] 보다 작은 것을 찾는다. (floor value)
- 구체적으로 다음 세가지 조건을 검사한다.
- Case 1. A[i]이 모든 active list의 end candidates 중에서 가장 작다면, 새로운 (길이 1의) active list를 만든다.
- Case 2. A[i]가 모든 active list의 end candidates 중에서 가장 크다면, 기존의 가장 큰 active list를 복사해서 A[i]를 덧붙인다.
- Case 3. A[i]가 위의 두 경우가 아니라면 (즉, 가장 작지도 가장 크지도 않다면), A[i]보다 작으면서 가장 큰 end element를 가진 list를 찾아서 복사한 뒤 A[i]를 덧붙인다. (요기까지만 보면 case 2가 case 3에 포함됨) 그리고 새로 만들어진 이 list와 같은 길이의 list들은 모두 버린다.
단, 여기서 Case 1은 Case 3의 특별한 경우라서 따로 처리하지 않아도 무방하다.
절대 명제
|
작은 list의 end element는 큰 list의 end element 보다 작다. |
예제
- A = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}의 예를 통해서 따라가보자.
|
A[0] = 0. Case 1. There are no active lists, create
one. |
- 위의 예에서 보면, active list의 모든 원소를 가지고 있을 필요가 없다. 각 list의 마지막 원소만 가지고 있으면 된다. 그렇게 하면 LIS의 길이도 알 수 있고 마지막 원소들을 묶으면 LIS도 된다. (왜냐하면 큰 리스트의 마지막 원소는 작은 리스트의 마지막 원소보다 크기 때문이다) 따라서 이 경우 discarding은 마지막 원소의 replace가 되고 clone and extend는 그냥 appending이 된다.
- 이를 위해 보조 array가 필요한데 LIS를 구하는 array이므로 최대 크기는 원래 array의 크기 N이다. 그리고 어떤 값으로 replace하기 위해서는 보조 array에서 그 값의 ceiling값을 찾아야 한다. (여기서 search를 위해 log N 기법이 적용된다) 아울러 보조 array의 길이를 알고 있어야 한다. (그 값이 LIS 값이기 때문이다)
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <stdio.h> // Binary search int indexOfCeiling(int arr[], int l, int r, int key) { while (l < r) { int m = (l + r) / 2; if (arr[m] >= key) r = m; else l = m + 1; } return r; } // Returns true if there is a subset of set[] with sun equal to given sum int lis(int arr[], int n) { int* tails = new int[n]; int length = 1; // always points empty slot in tail tails[0] = arr[0]; for (int i = 1; i < n; ++i) { if (arr[i] > tails[length - 1]) // arr[i] extends largest subsequence tails[length++] = arr[i]; else { // arr[i] will become end candidate of an existing subsequence or // Throw away larger elements in all LIS, // to make room for upcoming greater elements than arr[i] // (and also, arr[i] would have already appeared in one of LIS, // identify the location and replace it) tails[indexOfCeiling(tails, 0, length - 1, arr[i])] = arr[i]; } } delete[] tails; return length; } int main() { int arr[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Length of LIS is %d\n", lis(arr, n)); return 0; } |
- code를 통해 tails[]가 어떻게 변화하는지 아래 그림을 통해 알아보자.
- 그리고 어떤 값의 ceiling index를 알려주는 함수 indexOfCeiling()의 동작 원리를 아래 그림을 통해서 확인할 수 있다. 아래 그림은 {1, 3, 5, 7, 9} 가 있을 때 입력 값 2, 5, 0, 8에 대한 ceiling값의 index를 반환하는 과정을 보여주고 있다.
