최장 증가 부분 수열

최장 증가 부분 수열(LIS)

 

동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다.

 

 

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.
이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다.

 

O(n^2) 방법

 

for (int i = 0; i < n; i++) {
    if (dp[i] == 0)dp[i] = 1;
    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j]) {
            if (dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }
}

 

 

매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값 +1을 업데이트하는 방식으로 처리를 한다면,
N번을 확인하면서 최댓값을 찾는데 O(NlogN)시간이 걸린다.

 

lower_bound를 이용한다.
찾고자 하는 값 이상이 처음 나오는 위치를 리턴한다.

for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    if (vt.back() < x) {
        vt.push_back(x);
           ans++;
    }
    else {
        auto it = lower_bound(vt.begin(), vt.end(), x);
        *it = x;
    }
}

it가 x값보다 이상인 값이 처음 나오는 위치를 가리키게 되고 그 장소에 x값을 대입한다.

lower_bound는 이분탐색을 이용해서 탐색하기 때문에 O(logN)의 시간이 걸린다.
총 N개의 원소에 대해서 실행하게 되므로
O(NlogN) 시간복잡도를 가진다.