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

알고리즘/LIS 알고리즘 (최장증가수열 알고리즘)

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

Source 2020. 2. 20. 21:13

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[] 배열의 형태를 보여준다

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

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