이분탐색

백준 12015 가장 긴 증가하는 부분 수열2 문제풀이

12015 가장 긴 증가하는 부분 수열2.
DP의 대표적인 문제인 LIS의 시간 복잡도를 줄여보자

문제상황 파악하기.

이 문제는 가장 긴 증가하는 부분 수열1 보다 N이 1000배 정도 늘어났다.
따라서 같은 방법으로 풀면 TLE(Time Limit Exceeded)를 받게 된다.
그러면 시간 복잡도를 O(NlogN)까지 줄여서 풀어야한다. 그 때 이분탐색의 아이디어를 얻게 된다.
거기까지 알 수 있었는데 과연 이제 어떻게 이분탐색으로 풀어야할까?

아이디어 얻기.

이분탐색을 하려면 정렬이 되어있는 자료여야한다.
그렇다면 어떤 자료를 정렬하여 쓸 수 있는지 확인해보자! 먼저 수열 그 자체는 정렬하면 의미가 퇴색되므로 정렬할 수 없다.
하지만 찾고 있느 증가하는 부분수열은 정렬되어있다!
이 아이디어를 끌고 나가보았는데 쉽지만은 않았다.
그래서 게시판 질문들을 참고했는데 증가하는 부분수열의 요소으 값은 무시하고 배열의 길이만 찾는것을 확인 할 수 있었다.

그렇다면 이분탐색을 이용해 가장 긴 수열의 길이를 찾아보자

대체가 가능한 이유는 더 길어지면 그것이 제일 긴 수열이 되는거고 넘어가지 않으면 이전 것이 최대가 되는것이기 때문이다.

주의할 점

나는 구현을 하다가 InvalidNextSize free(): invalid next size 를 만났다. 동적배열을 free시켜주는 과정에서 문제가 발생한 것이다. 또한 이분탐색 구현 중 맨처음 넣어둔 매우 작은 수가 대체되는 경우가 생겨 틀리는 경우가 생겼다.
이분 탐색 구현의 경게값을 확인하며 off-by-one Error를 조심하자.

실제코드

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

using namespace std;

vector<int> arr;        //입력받는 수열
vector<int> nowlongest; //가장긴 부분수열의 길이를 구하기 위한 배열

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    for(int i=0;i<n;i++){
        int num;
        cin >> num;
        arr.push_back(num);
    }
    
    nowlongest.push_back(-987654321);   //충분히 작은값을 넣어준다.
    
    for(int i=0;i<n;i++){
        if(nowlongest.back()<arr[i]){
            nowlongest.push_back(arr[i]);
        }else{
            int lo=0,hi= nowlongest.size();
            while (lo+1<hi) {
                int mid = (lo+hi)/2;
                
                if(nowlongest[mid]>=arr[i]) hi = mid;
                else lo = mid;
            }
            
            nowlongest[hi] = arr[i];
        }
    }
    
    cout << nowlongest.size()-1;
}