LIS를 구하는 두 가지 방법

LIS(Longest Increasing Subsequence) 문제를 해결하기 위하여 잘 알려진 방법으로는 두 가지 방법(동적 계획법, 이진 탐색)이 있다. 여기서 전체 배열의 길이가 n 일때, 동적 계획법을 사용할 경우 시간 복잡도는 O(n²)이며 이진 탐색을 사용할 경우 시간 복잡도는 O(nlog₂n)이다. 세그먼트 트리를 사용해서도 LIS 문제를 해결할 수 있으나 시간 복잡도가 이진 탐색을 사용할 경우와 같으므로 아래에서는 동적 계획법과 이진 탐색만을 각각 사용하여 LIS 문제를 어떻게 해결하는지 살펴보겠다.

1. 동적 계획법

구현하기 가장 쉬우며 n이 그리 크지 않은 경우에만 사용할 수 있다. 길이가 6인 배열 A가 있다고 가정해보자. 그리고 메모이제이션을 위한 배열 dp도 함께 생각해보자. dp의 각 원소는 모두 1로 초기화되어 있다. 아래에서는 동적 계획법을 사용하여 어떻게 문제를 해결하는지에 대해 설명하였다.

A: 10 20 10 30 20 50  /  dp: 1

A의 첫 번째 원소 A₁(10) 앞에는 아무런 원소가 없다. 따라서 아무런 변화가 일어나지 않는다.

A: 10 20 10 30 20 50  /  dp: 1 2

A₂부터는 앞 원소와 크기를 비교해가며 메모이제이션을 진행한다.

A₂(20)의 앞에는 10이 있으며 10 < 20 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A: 10 20 10 30 20 50  /  dp: 1 2 1

A₁(10)과 비교하면 10 = 10 이므로 아무런 변화가 없다.

A₂(20)과 비교하면 20 > 10 이기 때문에 아무런 변화가 없다.

A: 10 20 10 30 20 50  /  dp: 1 2 1 3

A₁(10)과 비교하면 10 < 30 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A₂(20)과 비교하면 20 < 30 이므로 "A₂(20)의 부분 수열 길이 + 1"을 저장한다. (2 → 3)

A₃(10)과 비교하면 10 < 30 이지만 현재 dp 값(3)이 "A₃(10)의 부분 수열 길이 + 1"(2)보다 크기 때문에 아무런 변화가 없다.

A: 10 20 10 30 20 50  /  dp: 1 2 1 3 2

A₁(10)과 비교하면 10 < 20 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A₂(20)과 비교하면 20 = 30 이므로 아무런 변화가 없다.

A₃(10)과 비교하면 10 < 20 이지만 현재 dp 값(2)가 "A₃(10)의 부분 수열 길이 + 1"(2)와 같기 때문에 아무런 변화가 없다.

A₄(30)과 비교하면 30 > 20 이므로 아무런 변화가 없다.

A: 10 20 10 30 20 50  /  dp: 1 2 1 3 2 4

A₁(10)과 비교하면 10 < 50 이므로 "A₁(10)의 부분 수열 길이 + 1"을 저장한다. (1 → 2)

A₂(20)과 비교하면 20 < 50 이므로 "A₂(20)의 부분 수열 길이 + 1"을 저장한다. (2 → 3)

A₃(10)과 비교하면 10 < 50 이지만 현재 dp 값(3)이 "A₃(10)의 부분 수열 길이 + 1"(2)보다 크기 때문에 아무런 변화가 없다.

A₄(30)과 비교하면 30 < 50 이므로 "A₄(30)의 부분 수열 길이 + 1"을 저장한다. (3 → 4)

A₅(20)과 비교하면 20 < 50 이지만 현재 dp 값(4)가 "A₅(20)의 부분 수열 길이 + 1"(3)보다 크기 때문에 아무런 변화가 없다.

for (int i = 1; i <= n; i++) {

    dp[i] = 1;

    for (int j = 1; j < i; j++) {

        if (A[j] < A[i]) {

            dp[i] = max(dp[i], dp[j] + 1);

        }

    }

    ans = max(ans, dp[i]);

}

cout << ans << '\n';

최종적으로 dp 배열에서 가장 큰 값인 4가 최장 증가 수열의 길이 값이다.

2. 이진 탐색
위 1번 방법으로 LIS 풀이를 시도하면 LIS의 길이 값은 얻을 수 있지만, LIS를 구성하는 실제 원소들은 얻을 수 없다. 그리고 n이 10000이 넘어가기 시작하면 빠른 시간 내에 답을 얻기가 힘들다. 이진 탐색을 사용하면 시간 복잡도를 O(nlog₂n)으로 줄이면서 실제 LIS도 얻을 수 있다. 실제 LIS를 얻을 수 있으므로 LIS 길이 값은 당연히 따라온다. 1번 방법때처럼 길이가 6인 배열 A가 있다고 가정하며 메모이제이션을 위한 벡터 dp도 함께 생각해보자. dp는 처음에 완전히 비어있는 벡터이다. 아래에서는 이진 탐색을 사용하여 어떻게 문제를 해결하는지에 대해 설명하였다.

LIS의 길이를 구하기 위해서 배열 A의 각 원소 A_i를 처음부터 끝까지 훑으며 아래의 조건에 따라 dp 벡터에 값을 넣는다.

1) dp 벡터의 맨 끝값이 A_i 미만인 경우 → dp 벡터의 맨 끝에 A_i를 삽입

2) dp 벡터의 맨 끝값이 A_i 이상인 경우 → dp 벡터의 lower_bound(A_i) 자리에 A_i를 삽입

A: 10 20 10 30 20 50  /  dp: 10

A: 10 20 10 30 20 50  /  dp: 10 20

A: 10 20 10 30 20 50  /  dp: 10 20

A: 10 20 10 30 20 50  /  dp: 10 20 30

A: 10 20 10 30 20 50  /  dp: 10 20 30

A: 10 20 10 30 20 50  /  dp: 10 20 30 50

최종적으로 dp 벡터의 길이 값(4)가 최장 증가 수열의 길이 값이다. 다만, dp 벡터의 내용(10, 20, 30, 50)이 반드시 LIS는 아니다. 왜냐하면, dp 벡터의 중간에 위치한 값들은 배열 A의 끝에 도달하기 전에 계속해서 바뀔 수 있기 때문이다. 위의 예에서는 운이 좋아서 실제 LIS가 도출되었지만 실제로는 위의 방법만으로 LIS를 구할 수 없다. 즉, 추가적인 과정이 필요하다. dp 벡터에 새로운 값이 들어갈 때 바로 앞 원소의 인덱스를 저장하는 backtrace 벡터를 새로 생성한다. 이후 dp 벡터에 새로운 값을 넣을 때 자신의 앞 원소의 인덱스를 backtrace 벡터에 저장하면 된다.

#include <bits/stdc++.h>

using namespace std;

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {

    return a.first < b.first;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin >> n;

    vector<pair<int, int>> A;

    for (int i = 0; i < n; i++) {

        int tmp;

        cin >> tmp;

        A.push_back({ tmp, i });

    }

    const int max_sz = 1e6 + 1;

    vector<pair<int, int>> dp(1, { -2e9, -1 });

    vector<int> backtrace(max_sz, -1);

    for (auto& p : A) {

        if (dp.back().first < p.first) {

            backtrace[p.second] = dp.back().second;

            dp.push_back(p);

        }

        else {

            auto iter = lower_bound(dp.begin(), dp.end(), p, cmp);

            backtrace[p.second] = (iter - 1)->second;

            *iter = p;

        }

    }

    cout << dp.size() - 1 << '\n';

    vector<int> ans;

    for (int i = dp.back().second; i >= 0; i = backtrace[i]) {

        ans.push_back(A[i].first);

    }

    for (int i = ans.size() - 1; i >= 0; i--) {

        cout << ans[i] << ' ';

    }

    cout << '\n';

    return 0;

}

이런 방법이 가능한 이유는 dp 배열에 A_i가 삽입되는 자리의 바로 앞 값을 끝으로 하는 가장 긴 수열이 backtrace 벡터에 저장된 인덱스를 따라 이어져 있을 것이기 때문이다.