LIS(Longest Increasing Subsequence) - 최장 증가 수열

LIS(Longest Increasing Subsequence) 알고리즘이란 번역하자면 최장 증가 수열이다.

예를들어 1,4,6,2,3,4,9,8 이런 수열이 있다고 하면 이 수열의 LIS는 1,2,3,4,8이 될 것이다.

이러한 LIS알고리즘을 구현하는 방법은 크게 2가지가 있는데 

1) O(N^2)의 방법

2) O(N*logN)의 방법 으로 나누어 볼 수 있다.

먼저 O(N^2)의 방법이다. 가장 간단하고 직관적으로 알 수 있는 방법으로 자기 자신을 기준으로 자신 앞에 있는 모든 수를 다 확인해보는 방법이다.

주어진 수열에서 개수를 x는 1~x-1까지의 모든 수열중 자신보다 작은 개수의 최대값 +1을 해주는 과정이다. 또한 최장 증가 수열에 포함되는 수들을 확인하기 위해서는 

해당 그림처럼 각각의 개수를 저장할 때 자신보다 작은 이전의 값중에 최대개수가 있던 index의 위치를 같이 저장을 해두면 된다.

하.지.만!......... 만약 N의 크기가 10만을 넘어가게 된다면 ... 보통 PS는 문제는 제한 시간내로 해결하지 못하는 경우가 많게 된다. 따라서 O(N*logN)의 시간복잡도를 가지는 방법이 필요한 것이다. 

O(N*logN) 구현의 핵심적인 방법은 LIS의 마지막 값이 추가하는 값보다 크면 추가를 하고, 그렇지 않다면 이진탐색(lower_bound)을 이용하여 LIS내의 배열의 값보다 수 중 가장 작은 수와 교체하는 방법이다. 코드를 통해 쉽게 이해해보도록 하자 

 vt.push_back(-INF);
 for (int i = 0; i < n; i++) {
     int x = v[i];
     if (vt.back() < x) {
         vt.push_back(x);
         ans++;
     }
     else {
         auto it = lower_bound(vt.begin(), vt.end(), x);
         *it = x;
     }
 }

이런식으로 추가하는 수가 LIS의 마지막 수보다 클 경우 추가해주고, 그렇지 않을 경우에는 해당 위치를 lower_bound를 통해 찾고 바꾸어 준다. 

여기에다가 LIS의 구성 원소를 O(N*logN)에 구할수 있는 방법 또한 있다. O(N^2)에서 했던것처럼 LIS의 구성요소가 추가되거나, 또는 수정이 될 때 추가/수정이 된 원소의 Parent를 그 원소 앞부분으로 해주는 방식이다. 

예를들어 4,2,6,7,9,1,3,10 라는 수열이 있다고 하자. Parent는 전부 -1로 초기화를 하고 진행한다면 

1) 처음 4는 앞에 원소가 없으므로 pass

2) 2의 경우 수정은 되지만 앞에 원소가 없으므로 또한 pass

3) 그 다음 6의 경우 추가가 되고 앞에 2가 있으므로 parent[6] = 2 ... 이런식으로 쭉 채워나가다 보면 아래와 같이 채워질 것이다.

여기서 LIS는 최종적으로 1,3,7,9,10이 되는데 LIS의 원소는 제일 마지막 수인 10에서만 역추적을 해나가면 된다. 

vector<int> cand(n); //값이 입력된 배열
vector<int> LIS;
vector<int> parent(500001,-1);
 
LIS.push_back(cand[0]);
 
for(int i=1; i<n; ++i){
    if(LIS.back() < cand[i]){
        parent[cand[i]]=LIS.back();
        LIS.push_back(cand[i]);
    }
    else{
        auto it=lower_bound(LIS.begin(), LIS.end(), cand[i]);
        *it=cand[i];
        if(it!=LIS.begin())
            parent[cand[i]]=*(--it);            //이부분에서 Parent 업데이트!!!!
    }
}
 
int child=LIS.back();
while(child!=-1){
    printf("%d\n", child);
    child=parent[child];
}

아주 깔끔하죠잉~ 

추가) 왜 가장 마지막의 원소에서 역추적을 할까 ?