[백준 12015] 가장 긴 증가하는 부분 수열 2

 

 아마 알고리즘을 따로 공부했거나, 학부 과정에서 컴퓨터 알고리즘 과목을 수강했다면 익숙할 LIS 문제이다. 대표적인 DP 문제인데, 직관적으로 떠올릴 수 있는 형태의 DP 알고리즘의 시간복잡도는 O(n^2)로 이 문제를 풀기에는 부적합하다. 접근 방식을 조금 바꿔야 하는데, 나는 DP 문제에 약한 편이라 아무것도 모르는 체로 이 문제를 접했다면 발상에 꽤나 애먹었을 것 같다.

 

 먼저 시작은 O(n^2)인 알고리즘에서 매번 dp[0]~dp[i-1]까지를 모두 확인하고 싶지 않다는 생각에서 출발한다. LIS를 구성하기 위해 배열을 탐색한다고 할 때, 앞서 나온 LIS의 가장 마지막 원소보다 탐색 중인 원소가 더 크다면 LIS에 바로 추가하면 된다는 것은 자명하다.

 하지만 LIS의 가장 마지막 원소보다 탐색 중인 원소가 작다면? 판단하기 애매해진다. 배열의 원소 구성에 따라 앞서 만들어온 LIS가 무용지물인 경우도 있고, 오히려 탐색 중인 원소를 포함해 뒤에 나올 원소를 모두 이용해도 앞서 나온 LIS가 더 길 가능성도 있다. 그래서 기존 LIS의 일부 혹은 모두를 버리고 현재 탐색 중인 원소를 포함해 새로운 LIS를 만들어 나갈지 아니면 탐색 중인 원소를 버릴지는 당장 정할 수 없다.

 그러나 하나는 확실하다. 앞서 나온 원소들과 현재 탐색 중인 원소를 이용해서 같은 길이지만 마지막 원소가 더 작은 LIS를 만들 수 있다면, 이는 무조건 정답에 가까워지는 선택이다. 그러니까 [40, 100, 200, 70, ...] 와 같은 형태의 배열이 있다고 하고 현재 70을 탐색중이라고 하면, 앞서 나온 LIS는 [40, 100, 200]이다. 이 때, 길이가 2인 LIS는 [40, 100]인데, 이것보다 현재 탐색 중인 원소를 이용해 [40, 70]으로 구성하는게 유리하다.

 

 따라서 배열을 처음부터 탐색하면서, dp 배열에 특정 구간에 만들 수 있는 길이별 LIS의 마지막 값을 계속 갱신해주고, 최종적으로 만들 수 있는 LIS의 최대 길이를 출력하는 형태로 문제를 해결할 수 있다. 그렇다면 탐색 중인 원소가 들어갈 위치는 어떻게 계산할 수 있을까? 로직 상 dp 배열에서 뒤의 원소는 무조건 앞에 있는 원소들보다 큰 값을 가지는 형태이므로, 이진 탐색으로 lower bound를 찾아 그 값을 대체해주면 된다. 물론 만들고 있던 LIS의 마지막 값보다 탐색 중인 값이 크다면 dp배열의 마지막에 탐색 중인 값을 삽입하면 된다.

 위의 과정에서 주어진 배열을 선형 탐색하고(O(n)), 매 탐색 과정에서 삽입 혹은 대체를 위한 이진 탐색이 발생하므로(O(log n)), 시간복잡도는 O(n log n)이 된다.

 

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

using namespace std;

int arr[1000000];

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

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

    vector<int> dp;
    dp.push_back(arr[0]);

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

    cout << dp.size();
}