[C++] 12015번 가장 긴 증가하는 부분 수열 2 - 이분 탐색, 가장 긴 증가하는 부분 수열

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

#define LOOP(i, N) for(int i=1; i<=N; i++)

using namespace std;

int N;  //수열의 크기 N
vector<int> num = {987654321};  //수열

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    LOOP(i, N) {
        int x;
        cin >> x;
        if(x>num.back()) num.push_back(x);
        else
            num[lower_bound(num.begin(), num.end(), x) - num.begin()]=x;
    }
    cout << num.size();
    
    return 0;
}

최장 증가 부분 수열 O(NlogN)을 새로 배워서 해봤다. 맨 처음에는 이분 탐색 직접 구현하려다가 던졌는데 찾아보니 lower_bound()라는 좋은 함수가 있었다. 똑같이 O(log n)이니까 편하게 쓰면 될 것 같다.

 

<알고리즘>

최장 증가 부분 수열의 길이가 k인 제일 마지막 수를 메모함으로써 자신보다 작은 숫자에 추가해 더 긴 수열을 만드는 방법으로 O(NlogN)으로 해결 가능하다.

 

<최장 증가 부분 수열>

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

최장 증가 부분 수열 - 나무위키

 

<lower_bound()>

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기