LIS를 O(n^2)이 아닌 O(nlogn)으로 접근하는 방법

https://dyngina.tistory.com/16

을 참고하여 작성하였습니다.

이 글은 저만의 공부를 위하여 간단 요약한 것입니다.

위의 원글을 보시길 바랍니다.

※ lower_bound를 활용한 LIS 풀이법

단점은 답 밖에 모른다.

경로 역추적은 다른 방법을 쓰자.

배열(또는 벡터) 내에서 증가 수열을 유지할 수 있는 최적의 장소를 

lower bound를 이용하여 찾아준다.

vector<int> v = {10, 20, 40, 30, 70, 50, 60};

1. 10을 넣는다. 이 때의 v.size() = 1

현재 : v = {10}

2. 20을 넣는다. 이 때의 v.size() = 2

현재 : v = {10, 20}

3. 40을 넣는다. 이 때의 v.size() = 3

현재 : v = {10, 20, 40}

4. 30을 넣는다. 이 때, 40이 있는 자리에 30으로 치환한다.

현재 : v = {10, 20, 30}

5. 70을 넣는다. 이 때, v.size() = 4

현재 : v = {10, 20, 30, 70}

6. 50을 넣는다. 이 때, 70이 있는 자리에 50으로 치환한다.

현재 : v = {10, 20, 30, 50}

7. 60을 넣는다. 이 때, v.size() = 5

현재 : v = {10, 20, 30, 50, 60}

이 때, 최종적으로 v.size()의 값이 

LIS의 최대 길이가 된다.

참고 문제

BOJ 2352번 반도체 설계

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

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 40001
 
int n;
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    int input;
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
 
        int idx = lower_bound(v.begin(), v.end(), input) - v.begin();
 
        // 찾을 자리가 없다면(찾을 자리가 없다는 것은 idx의 값이 v.size()와 같다.)
        if (idx == v.size()) {
            v.push_back(input);
        }
        else {
            // 위치를 찾았다면 그 곳에 원래 있던 값 대신에 input을 넣어준다.
            v[idx] = input;
        }
    }
 
    printf("%d\n", v.size());
 
    return 0;
}