백준 12738 가장 긴 증가하는 부분수열 3 - C++, LIS

12015번: 가장 긴 증가하는 부분 수열 2

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

int n, input;

int main(){
    scanf("%d", &n);
    vector<int> num;

    for(int i = 0; i < n; i++){
        scanf("%d", &input);

        if(num.empty() || num.back() < input)
            num.push_back(input);
        else {
            auto temp = lower_bound(num.begin(), num.end(), input);
            *temp = input;
        }
    }
    
    printf("%d\n", num.size());
}

---

 이전에 시리즈 1탄을 풀이하고 나서 오랜만에 풀어보는 LIS 알고리즘입니다. 위 문제의 경우 테스트 케이스 양이 많기 때문에 2중 포문을 통한 O(N^2) 알고리즘으로는 안되고 O(Nlogn) 알고리즘을 사용해야 합니다.

 자세한 내용은 따로 정리를 할거라 생략하고 위 알고리즘은 하나씩 입력값을 받으며 정답 백터인 num에 넣어주는 것으로 새 입력값이 기존 벡터의 제일 큰 값보다 크면 뒤에 넣고 만약 아니라면 벡터의 원소들 중 어느 위치에 들어갈 수 있는지 확인하고 이를 교체하는 방식입니다.