[알고리즘 정리] 최장 증가 수열(LIS,Largest Increasing Sequence) 알고리즘

최장 증가 수열이란 주어진 수열의 부분수열중 가장 긴 증가 하는 수열을 말합니다.

예를들어,  다음과 같은 10개 원소의 수열에서

1, 3, 4, 5, 6, 9, 10의 7의 부분 수열이 가장 긴 증가 하는 수열입니다.

DP를 사용한 아이디어로서, 이분탐색을 이용하여 O(NlogN)의 시간복잡도로 해결합니다.

앞에서 부터 뒤로 O(N)으로 탐색을 하고

 현재 원소의 놓여질 최적의 자리를 찾는데 이분탐색을 이용하여 O(logN)이 걸립니다.

1. 처음 벡터에 -INF를 넣어줍니다.

2. 벡터의 맨 뒤의 값보다 넣으려는 1이 크기 때문에(-INF<1) 맨뒤에 추가

3. 벡터의 맨 뒤의 값보다 넣으려는 7이 크기 때문에(1<7) 맨뒤에 추가

4. 벡터의 맨 뒤의 값보다 넣으려는 3이 작다면 lower_bound()함수를 사용하여 자기(3)보다 작은 값(1) 뒤에 넣습니다.

5. 벡터의 맨 뒤의 값보다 넣으려는 4가 크기 때문에(3<4) 맨뒤에 추가

6. 벡터의 맨 뒤의 값보다 넣으려는 2이 작다면 lower_bound()함수를 사용하여 자기(2)보다 작은 값(1) 뒤에 넣습니다.

7. 벡터의 맨 뒤의 값보다 넣으려는 8이 크기 때문에(4<8) 맨뒤에 추가

8. 벡터의 맨 뒤의 값보다 넣으려는 5이 작다면 lower_bound()함수를 사용하여 자기(5)보다 작은 값(4) 뒤에 넣습니다.

9. 벡터의 맨 뒤의 값보다 넣으려는 6이 크기 때문에(5<6) 맨뒤에 추가

10. 벡터의 맨 뒤의 값보다 넣으려는 9가 크기 때문에(6<9) 맨뒤에 추가

11. 벡터의 맨 뒤의 값보다 넣으려는 10이 크기 때문에(9<10) 맨뒤에 추가

코드는 간단합니다.

https://www.acmicpc.net/problem/2352

int n,m,ans=0;
vector<int> v;

int main()
{
    scanf("%d",&n);
    v.push_back(-INF);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&m);
        if(v.back()<m)
        {
            v.push_back(m);
            ans++;
        }
        else
        {
            auto it=lower_bound(v.begin(), v.end(),m);
            *it=m;
        }
    }
    printf("%d",ans);
    return 0;
}