백준 3745 ) 오름세 골드 2 LIS(n log n)

 

풀이: 오름세 문제를 읽어보면 LIS(최장 증가 부분 수열)를 찾는 것이다.  아래가 정의이다

 

이걸 사람 눈으로만 찾는다고 치자 (1 4 5 3 9 3 8 10) 가 예시라면 늦어도 30초 안에는 찾을 수 있을 것이다

하나의 수열을 찾았다면 길이가 최장 수열이 하나가 아닐수도 있으니 하나 더 찾아보도록 바란다;;;

 

일단 n이 10만까지 들어올 수 있으니 사람 눈으로는 절대 못찾는다

LIS는 보통 2가지로 방법으로 찾을 수 있다 실버수준의 O(n * n)의 시간 복잡도와 골드 수준의 O(n log n)가 있다

 

실버수준이라면 n이 10만인 경우를 하나만 입력받아도 10만 * 10만은 100만은 아니고 100억정도 연산하는거다

 

당연히 안된다 그래서 골드 수준의 방식을 쓰면 10만 * 로그 10만이라  아래 와 같다고 한다

 

arr이라는 배열에 데이터가 10 20 5 1 2 5 라고 하자

 

dp라는 빈 vector을 생성하고 일단 0번째 값(10) 을 넣는다

 

그리고 1부터 n-1까지 for문을 돌려준다 그 안에 조건문이 핵심이다

 

i = 1일 때 

dp.back()  = 10, arr[i] = 20이다  arr[i]가 10보다 더 크니까 vector에 20을 넣어준다

 

i = 2일 때 

dp.back() = 20, arr[i] = 10이다 arr[i]가 dp의 마지막 값보다 작으니까

lower_bound를 사용하여 dp안의 내용중에 arr[i]보다 크거나 같은 첫번째 값의 위치를 찾아 arr[i]의 값으로 대입한다

현재 dp: 5 20 

 

i = 3일 때 

dp.back() = 20, arr[i] = 1이다 arr[i]가 dp의 마지막 값보다 작으니까

 

현재 dp: 1 20 

 

i = 4일 때 

dp.back() = 20, arr[i] = 2이다 arr[i]가 dp의 마지막 값보다 작으니까

 

현재 dp: 1 2

 

이러한 방식으로 계속해준다 이해가 안 갈 수 있다 "아니 저게 왜  저렇게 되는거야?"

 

천천히 생각해보자 우리가 구하려는 것은 가장 긴 증가하는 수열의 크기이다

즉 dp안의 값을 생각하지 말고 dp.size()를 생각해라

 

뒤에 어떤 수들이 들어오든 어차피 기존의 dp의 기존 수보다 작은 수가 들어온다면 그 값을 바꾸기만 하는 것이고

size에는 전혀 지장이 가지 않는다 dp의 size는 i++을 하면서 현재까지의 가장 긴 증가하는 부분 수열의 크기일 뿐이다

arr[i]가 dp의 최대값보다 크다면 무조건 index적으로 뒤에 오는 수이기 때문에  push_back을 한다

 

쉬운 예) 만약 arr이 -> 10 11 12 13 1 2 3 5 6인 상황이더라도 아래를 보면 쉽다

 

10 

10 11

10 11 12

10 11 12 13

10 11 12 13 

01 11 12 13

01 02 12 13

01 02 03 05

01 02 03 05 06

 

마지막으로 코드를 보면 dp의 사이즈는 작아질 경우는 없다 즉 뒤로 갈수록 크기가 커지면 몰라도 작아지는 것은 없다

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

using namespace std;


int main() {
    while(true) {
        int n;

        cin >> n;

        if(cin.eof()) break;

        vector<int> arr(n);
        vector<int> dp;


        for(int i = 0; i < n ; i++) {
            cin >> arr[i];
        }

        dp.push_back(arr[0]);

        for(int i = 1; i < n; i++) {
            if(dp.back() < arr[i]) {
                dp.push_back(arr[i]);
            }
            else {
                int pos = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
                dp[pos] = arr[i];
            }
        }

        cout << dp.size() << "\n";
    }
}