[알고리즘] 가장 긴 증가하는 부분 수열 O(n log n) (이분 탐색 풀이)

[목차]

1. 완전 탐색과 DP로 푼 LIS
2. LIS 알고리즘
   1. 아이디어
   2. 알고리즘
   3. 알고리즘 분석
3. 예제
4. 정리

---

1. 완전 탐색과 DP로 구현한 LIS

이 전의 글에서는 LIS를 구하는 알고리즘을 완전 탐색과 동적 계획법으로 구현했었다. 동적 계획법 풀이는 O(N²)의 시간 복잡도를 가졌었다. 하지만 이분 탐색을 이용하면 O(N logN)의 시간 복잡도로 더 빠르게 해결할 수 있다.

 

이번 글에서는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로 구현해보려고 한다. 이분 탐색의 LIS를 이해하려면 이분 탐색의 lower_bound() 함수와 upper_bound()함수에 대해 알고 있어야 한다.  또한 DP로 푼 LIS알고리즘도 이해하고 오면 도움이 된다.

 

따라서 앞의 부분에 대한 이해가 안되어있다면 최소한 이분 탐색의 개념을 먼저 보고 오는것을 추천한다.

---

 

2. LIS 알고리즘(이분 탐색)

1)  아이디어

 

2) 알고리즘

 

3) 알고리즘 분석

 

4) 구현한 코드

 

[lowerBound함수를 직접 만들어 구현한 코드]

#include<iostream>
#include<vector>

using namespace std;

int N, cmp, arr[1000001];
vector<int> lis;

int lowerBound(int t){
    int st = 0;
    int en = lis.size();
    while(st < en){
        int mid = (st + en) / 2;
        if(lis[mid] >= t) en = mid;
        else st = mid + 1;
    }
    return st;
}

int main(void){
    cmp = -1000000001;
    cin >> N;
    for(int i=1; i<=N; i++) cin >> arr[i];
    for(int i=1; i<=N; i++){
        //추가하려는 값이 lis의 마지막보다 크면 추가하고 반대의 경우에는 lowerBound를 찾아 넣기
        if(arr[i] > cmp) lis.push_back(arr[i]);
        else lis[lowerBound(arr[i])] = arr[i];
        cmp = lis.back();

    }
    cout << lis.size();

    return 0;
}

[STL의 lower_bound를 사용하여 구현한 코드]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, cmp, arr[1000001];
vector<int> lis;

int main(void){
    cmp = -1000000001;
    cin >> N;
    for(int i=1; i<=N; i++) cin >> arr[i];
    for(int i=1; i<=N; i++){
        //추가하려는 값이 lis의 마지막보다 크면 추가하고 반대의 경우에는 lowerBound를 찾아 넣기
        if(arr[i] > cmp) lis.push_back(arr[i]);
        else lis[lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin()] = arr[i];
        cmp = lis.back();

    }
    cout << lis.size();

    return 0;
}

[LIS의 길이와 수열을 출력해주는 코드]

 

 

3. 예제

 

4. 정리