Binary Search

코드 (LIS)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

//이분탐색을 이용한 방법. subs는 실제 부분수열. num은 실제 부분수열이 아니다.

vector<int> subs;
int LIS(vector<int>& arr) {
    //num, idx는 한 묶음이다. pair 쓰기 귀찮아서 안 썼다.
    vector<int> num, idx; 
    vector<int> prev(arr.size(), -1);

    for (int i = 0; i < arr.size(); i++) {
        int pos;
        pos = lower_bound(num.begin(), num.end(), arr[i]) - num.begin();

        if (pos == num.size()) {
            num.push_back(arr[i]);
            idx.push_back(i);
        }
        else {
            num[pos] = arr[i];
            idx[pos] = i;
        }
        if (pos == 0) prev[i] = -1;
        else prev[i] = idx[pos - 1];
    }
    // 실제 부분 수열을 구한다.
    for (int i = idx[idx.size() - 1]; i != -1; i = prev[i])
        subs.push_back(arr[i]);
    reverse(subs.begin(), subs.end());

    return subs.size();
}

binary search 를 이용한 LIS(최장증가수열)

정리

관련 문제

참고 자료

• LIS - https://codedoc.tistory.com/414