Indexed tree를 사용하여 개의 원소를 포함한 수열에 대하여 의 시간복잡도로 개선할 수 있지만, 이를 이진 탐색을 이용하여 동일한 시간복잡도를 만들 수 있다.
이 방법은 LIS 배열을 활용한다. LIS 배열의 정의는 다음과 같다.
LIS[i] = 현재까지의 원소를 고려하여 길이를 i로 만들 수 있는 LIS의 마지막 원소
현재 n번째 원소까지 고려한 상태이고, n번째 원소까지 고려하여 만들 수 있는 최대 부분수열의 maxLength라 하고 LIS 배열에는 아래에서 설명할 규칙대로 잘 채워져 있다고 가정하자.
이제 n+1번째 원소를 고려하려 하는데, 이 이전에는 1부터 n번째 원소까지를 고려했기 때문에 우리는 순서에 대해 고려할 필요없이 “값”에 대해서만 비교를 하면 된다.
따라서 우리는 순서를 고려하지 않고 원소의 값만을 고려하여 LIS 배열을 갱신할 것이다. 이 때, 갱신되는 것은 다음 3가지 과정 중 하나만을 따르게 된다.
** 위의 세 가지 과정은 수열의 원소 나열 형태를 고려하여 더 빠르게 채울 수 있도록 분할한 것일 뿐이며, 3)의 규칙만으로도 모든 원소들에 대해 LIS 배열을 갱신할 수 있다.
아래 제시되는 소스는 3)의 규칙만으로 작성한 소스이다.
소스
// 최솟값에 대한 정의
const int MIN_INTEGER_VALUE = -100;
// 구간에 대한 정의
// s <= n <= e 를 만족하는 n의 범위를 [s,e] 라 한다.
// s < n < e 를 만족하는 n의 범위를 (s,e) 라 한다.
int binary_search(int Arrays[], int start, int end, int key) { // 탐색 범위는 [start,end) 이다.
if( start==end ) return start; // 탐색을 더 할 필요가 없는 경우
int middle = (start+end)/2;
if( Arrays[middle] < key ) { // [middle+1,end) 구간으로 범위 축소
return binary_search(Arrays,middle+1,end,key);
}
else if( Arrays[middle] > key ) { // [start,middle) 구간으로 범위 축소
return binary_search(Arrays,start,middle,key);
}
else return middle;
}
// key보다 크거나 같은 최소 원소의 위치를 return하는 이진 탐색 소스
int main() {
int N = 9;
int data[] = {6,2,9,8,3,4,1,7,4};
int LIS[N+1]; // LIS의 길이는 1이상 N이하이므로, 배열 크기는 N+1로 선언한다.
int maxLength = 0; // LIS 배열의 초기 높이.
LIS[0] = MIN_INTEGER_VALUE; // 편의상 최솟값을 가리키는 최소 원소를 삽입
for(int i=0 ; i < N;i++){
int position = binary_search(LIS,0,maxLength+1,data[i]); // 이진 탐색을 통해 삽입할 원소의 위치를 확인
LIS[position] = data[i]; // LIS 배열에 원소 갱신
if( maxLength < position ) maxLength = position; // maxLength 갱신
}
int ans = maxLength; // ans : maxLength
}
출처:Fate