LIS 알고리즘(최장 증가 부분 수열) $O(NlogN)$

 

 

 

 

   예전에 LIS알고리즘을 DP로 $O(N^2)$만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.

LIS $O(N^2)$

 

 이번 포스팅에서는 이분탐색을 활용한 $O(NlogN)$ LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제는 아래 세 개가 있다.

가장 긴 증가하는 부분 수열 2
가장 긴 증가하는 부분 수열 3 
가장 긴 증가하는 부분 수열 5

 

 LIS 길이 구현 방법

 외부 배열이나 벡터에서 각각의 숫자들의 lower bound를 구해 그 인덱스로 넣어주는 방식이다. 아래 그림은 LIS 이분탐색 과정이다.

출처 : Hyun/Log "[알고리즘] LIS(최장 증가 부분 수열)이란?

 이렇게 이분탐색으로 배열을 만들고 나면 크기 순서대로 숫자들이 정렬이 되어있다. 여기서 이 배열의 길이는 LIS의 길이와 같다. 여기서 주의해야할 점은 배열의 숫자들이 실제 부분 수열은 아니라는 것이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int A[1000000],N,LIS=1,r;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>A[i];
    }
    v.push_back(A[0]);
    for(int i=1;i<N;i++)
    {
        if(v[v.size()-1]<A[i])
        {
            LIS++;
            v.push_back(A[i]);
            continue;
        }
        r = lower_bound(v.begin(),v.end(),A[i]) - v.begin();
        v[r] = A[i];
    }
    cout<<LIS;
}

 

 LIS 수열 구현 방법

 LIS 길이 구현 방법과 거의 비슷한 방식으로 구현한다. 다만 추가적으로 각 숫자마다의 lower_bound를 저장하는 새로운 d배열이 필요하다. 

arr	3	5	7	9	2	1
lower_bound	0	1	2	3	0	0

 

 각각의 숫자마다 lower_bound값이 이렇게 나타났었는데 이를 어떤 배열에 저장해두자. 이 배열에서 맨 마지막부터 이터레이션을 할 것이다. 이터레이션 중 최초로 LIS - 1값 (여기서는 3)이 나오면 이 수(여기서는 9)를 저장한다. 이후에는 LIS-2가 나오면 저장하고, 다음에는 LIS-3 ..... 0까지 뒤에서부터 최초로 나오는 수들에 해당하는 수들을 stack이나 배열에 저장한다. 이제 이 수들을 출력해주면 해당하는 부분수열이 잘 나온다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int A[1000000], N, LIS = 1, r, check[1000001];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    
    v.push_back(A[0]);
    check[0] = 0;
    
    for (int i = 1; i < N; i++)
    {
        if (v.back() < A[i])
        {
            LIS++;
            v.push_back(A[i]);
            check[i] = LIS - 1;
        }
        else
        {
            r = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
            v[r] = A[i];
            check[i] = r;
        }
    }
    
    cout << LIS << "\n";
    
    vector<int> ans(LIS);
    int index = LIS - 1;
    
    for (int i = N - 1; i >= 0; i--)
    {
        if (check[i] == index)
        {
            ans[index] = A[i];
            index--;
        }
    }
    
    for (int i = 0; i < LIS; i++)
    {
        cout << ans[i] << " ";
    }
}