BOJ 14003. 가장 긴 증가하는 부분 수열 5

문제 링크

LIS(Longest Increasing Subsequence) 문제는 다이나믹 프로그래밍으로 해결할 수 있는 유명한 문제들 중 하나로, 다이나믹 프로그래밍을 이용한다면 $dp(i)$를 $i$번째 원소를 마지막 값으로 갖는 LIS의 길이로 정의한 뒤 $dp(n)$을 구해주면 되는데, 이때 $dp(i)$를 구하기 위해 $i$번째 원소 앞에 있는 배열의 원소와 $dp(j)$ 값을 스캔해야 하므로 시간 복잡도는 $O(n^2)$가 된다. 하지만 이 문제는 수열의 원소 개수가 최대 1,000,000개이므로 이 알고리즘을 사용한다면 시간 초과가 발생할 수밖에 없다.

이 문제를 $O(n log n)$의 시간 복잡도로 해결하는 알고리즘이 존재하는데, 바로 수열에 있는 수들을 각각 검사하면서, LIS가 될 수 있는 후보 수열을 저장하는 배열을 업데이트하는 방식으로 동작한다.

주어진 배열을 $A$, LIS가 될 수 있는 후보 수열을 저장하는 배열을 $B$라고 하자. 다음으로 $A$의 원소를 앞에서부터 하나씩 검사하며, 해당 원소 $a$가 $B$의 마지막 원소보다 크면 $B$ 마지막에 $a$를 삽입하고, 그렇지 않으면 C++의 lower_bound() 함수를 이용하여 $B$에서 $a$보다 크거나 같은 원소 중 index가 가장 작은 원소와 교체한다면 LIS의 길이를 늘릴 수 있는 가능성이 높아지게 된다.

이런 과정을 거치고 나면, $n$개의 원소에 대해 $O(log n)$의 시간 복잡도를 갖는 lower_bound() 함수가 실행되므로 $O(n log n)$의 시간 복잡도 안에 LIS의 길이를 찾을 수 있다.

하지만 lower_bound() 함수를 통해 주어진 수열의 수가 정렬된 상태를 항상 유지하는 $B$ 배열의 중간에 삽입되기 때문에, 실행이 끝나면 $B$ 배열은 LIS를 이루는 원소들에서 더 작은 값이 대체되어 있는 모양이 될 것이므로, $B$ 배열은 정확히 LIS의 원소들로만 이루어졌다고 볼 수는 없다.

즉 LIS를 이루는 정확한 요소를 알기 위해서는, $A$의 각 요소들이 $B$의 어떤 index에 삽입되었는지를 추적하는 새로운 배열 $C$를 만들고, 마지막에 $C$의 뒤쪽에서부터 수열의 순서를 보존할 수 있는 값들을 찾으면 된다.

// BOJ 14003. 가장 긴 증가하는 부분 수열 5

#include <cstdio>
#include <vector>
#include <algorithm>

std::vector<int> seq;

// A vector to keep track on the length of LIS.
std::vector<int> lis_elements;
// A vector to keep track on the result of lower_bound().
std::vector<int> lis_indices;
// A vector to build answer from lis_indices.
std::vector<int> answer;

int main() {
    int n;
    // Input
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        int x;
        scanf("%d", &x);
        seq.push_back(x);
    }
    // Solve
    for (int i=0; i<n; i++) {
        if (lis_elements.empty() || seq[i] > lis_elements[lis_elements.size() - 1]) {
            // seq[i] can be a new element of LIS, so attach to lis_elements.
            lis_indices.push_back(lis_elements.size());
            lis_elements.push_back(seq[i]);
        } else {
            // If seq[i] < lis_elements[pos], seq[i] can replace lis_elements[pos]
            // to have more possibility to increase length of LIS.
            int pos = std::lower_bound(lis_elements.begin(), lis_elements.end(), seq[i]) - lis_elements.begin();
            lis_indices.push_back(pos);
            lis_elements[pos] = seq[i];
        }
    }
    // The length of lis_elements is the length of LIS
    // since we increased the length of lis_elements only when new element is larger than max(lis_elements).
    // However, elements in lis_elements may not be elements of LIS,
    // since we did not keep order when replacing.
    // From the end of vector, we add first-seen elements of
    // index lis_elements.size() - 1, lis_elements.size() - 2...
    // to build LIS of length lis_elements.size() preserving order.
    int lis_index = lis_elements.size() - 1;
    for (int i=lis_indices.size() - 1; i>=0; i--) {
        if (lis_indices[i] == lis_index) {
            answer.push_back(seq[i]);
            lis_index--;
        }
    }
    std::sort(answer.begin(), answer.end());
    // Output
    printf("%d\n", lis_elements.size());
    for (int i: answer) printf("%d ", i);
    return 0;
}