[2][LIS : 최장증가수열 알고리즘] - Lower Bound 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)

2. Lower Bound 를 이용한 알고리즘

두번째로 알아볼 알고리즘은 Lower Bound를 이용한 알고리즘이다. 

 

시작하기에 앞서 Lower Bound란 정렬된 배열에서 찾고자 하는 값 이상이 처음으로 나타나는 위치를 말한다.

 

다음과 같은 배열에서 35의 lower bound는 40 이다.

 

위의 정의대로 처음으로 나타나는 자신보다 큰값 이라고 생각해도 되고

자신보다 큰 값들중 가장 작은 값 으로 생각해도 된다.

 

 

이 lower bound 알고리즘을 이분탐색으로 구현하게 될텐데 여기서는 lis[] 배열을 만들어서 사용할것이다.

 

lis[i] 의 정의는 (i+1)의 길이를 갖는 최대증가수열을 만들때, 가능한 가장 작은 수를 의미한다.

 

먼저 전체코드는 다음과 같다

 

int lis_lowerbound(int n){
    int i,j;
    int len = 0; // 현재 lis 배열의 마지막 원소 인덱스
    lis[0] = arr[0];
    for(i=1;i<n;i++){
        len = len + lower_bound(arr[i],len);
    }
    return len+1;
}


int lower_bound(int target, int len){ // 자신보다 큰 값들 중 가장 작은 값의 인덱스 리턴
    int start,end,mid;
    start = 0;
    end = len;
    if(target > lis[end]){
        lis[len+1] = target;
        return 1; // lis 배열에 새로 추가되었을때(최대증가수열의 값이 증가하였을때)만 1을 리턴해서 최종길이를 1씩 늘려준다
    }

    while(1){
        if(end-start == 1){ // 이분탐색중 두개의 원소만 남았을때
            if(lis[start] < target){
                lis[end] = target;
            }
            else{
                lis[start] = target;
            }
            return 0; // 기존의 값이 대체된것이므로 0을 리턴해서 최대길이를 늘리지않는다
        }
        if(end == start){ // lis의 원소가 1개일때
            if(lis[end] > target){
                lis[end] = target;
                return 0;  // 기존의 값이 대체된것이므로 0을 리턴해서 최대길이를 늘리지않는다
            }
        }
        mid = (start+end)/2;
        if(lis[mid] < target){
            start = mid;
        }
        else{
            end = mid;
        }
    }
    return 0; // 사실 while내에서 함수가 종료되기때문에 이값은 의미가 없다.
}

 

 

위 알고리즘에서 lis_lowerbound 내의 for문의 i가 아래 그림에서의 i이며 한번 for문을 수행할때마다 변화하는 lis[] 배열의 형태를 보여준다

 

 

i 가 증가함에 따라 변화하는 lis 배열

여기서 중요한점은 이 알고리즘이 끝난후 lis 배열의 원소개수가 최대증가수열 값을 의미하는것이지 그 배열자체가 최대증가수열을 말하지는 않는다. 즉 위 lis 배열의 최종적인 배열인 [10, 30, 50, 70] 이라는값이 이 예제에서는 우연히 최대증가수열이지만 항상 그것을 만족하지는 않는다. 그렇다면 LIS 의 값과 동시에 그값을 만족시키는 부분수열을 구하려면 어떻게 해야할까? 해당내용은 다음 포스팅에서 다룬다.

 

위의 과정을 자세히 살펴보면

 

 

 

 

i = 0
arr[0] = 20 이고 lis가 비어있으므로 20을 넣는다.

 

 

 

 

i = 1
arr[1] = 40 이고 lis 에서 40보다 큰 수가 없으므로 가장 뒤에 추가한다.

 

 

 

 

i = 2
arr[2] = 30 이고 lis 에서 30의 lower_bound는 40이 있는 자리이므로 40자리에 30을 넣는다

 

 

 

 

i = 3
arr[3] = 50 이고 lis 에서 50보다 큰 수가 없으므로 가장 뒤에 추가한다.

 

 

 

 

i = 4
arr[4] = 10 이고 lis 에서 10의 lower_bound는 20이 있는 자리이므로 20자리에 10을 넣는다

 

 

 

 

i = 5
arr[5] = 80 이고 lis 에서 80보다 큰 수가 없으므로 가장 뒤에 추가한다.

 

 

 

 

i = 6
arr[6] = 70이고 lis 에서 70의 lower_bound는 80이 있는 자리이므로 80자리에 70을 넣는다

 

위의 알고리즘을 사용하면 i가 n번 순회(O(N))하면서 이진탐색(O(logN))을 하므로 

O(NlogN) 의 시간복잡도를 가지게 된다.

 

따라서 이전 포스팅에서 다뤘던 DP를 이용한 N^2 LIS 알고리즘보다 훨씬 빠른 속도를 보이며

1000000의 길이를 가진 랜덤배열에서

약 0.19초만에 LIS 값을 찾아낸다.

 

n=1000000일때 c언어를 이용한 Lower_bound LIS 알고리즘의 실행속도