최장 증가 부분 수열(Longest Increasing Subsequence)

개념

최장 증가 부분 수열(Longest Increasing Subsequence)란, 수열에서 가장 긴 부분 수열을 의미한다.

위 수열에서 LIS는 [1, 3, 4, 7, 8]이며, 길이는 5가 될 것이다. 아래에 LIS의 길이와 LIS를 구하는 알고리즘을 서술한다.

DP - $O(N²)$

다이나믹 프로그래밍을 사용하여 Array의 LIS의 길이를 구하는 알고리즘은 이러하다.

LIS[i]: i번째 원소를 마지막으로 하는 LIS의 길이
LIS[i]: 0 <= j < i, Array[j] < Array[i]인 LIS[j]의 최댓값 + 1

각 원소에 대한 LIS를 구한 후 LIS의 최댓값이 최장 증가 부분 수열의 크기다.

전체 배열을 순회하는 데에 $N$, 각 i마다 LIS[j]의 최댓값을 구하는 데에 한 번 더 순회하니 $N$이 걸리므로 알고리즘의 시간복잡도는 $O(N²)$다. 아래의 백준 문제를 이 알고리즘을 사용하여 해결 가능하다.

백준 #11053 가장 긴 증가하는 부분 수열

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<int> arr(N);
    vector<int> lis(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        int maxVal = 0;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                maxVal = max(maxVal, lis[j]);
            }
        }
        lis[i] = maxVal + 1;
    }
    cout << *max_element(lis.begin(), lis.end());
    return 0;
}

이분 탐색으로 길이만 - $O(NlogN)$

DP를 사용하면 $O(N²)$의 시간복잡도를 가지기 때문에 N이 커지면 시간 내에 문제를 못 풀 수 있다. 이때 algorithm 헤더 안의 lower_bound($logN$)를 사용하면 시간복잡도를 줄일 수 있다.

• lower_bound: [first, last) 안의 key보다 크거나 같은 최소 iterator를 반환. 없다면 last 반환.

알고리즘은 다음과 같다.

LIS 벡터를 기준으로

1. LIS가 비어있을 경우
   LIS에 Array[0] push
2. LIS의 마지막 원소 > Array[i]일 경우
   LIS에 Array[i] push
3. LIS의 마지막 원소 <= Array[i]일 경우
   LIS에서 처음으로 Array[i]보다 크거나 같은 원소가 등장하는 곳(lower_bound 사용)

최종적으로 완성된 LIS 벡터의 길이가 최장 증가 부분 수열의 길이다. 다만, LIS에 저장된 값은 실제 LIS와 차이가 있다. 위의 예에서는 [1, 2, 4, 7, 8]이 저장됐지만 실제 LIS는 [1, 3, 4, 7, 8]로 차이가 있다.

전체 배열을 순회하는 데 $N$, 1lower_bound1를 찾는 데 $logN$이 걸리니 알고리즘의 시간복잡도는 $O(NlogN)$이다. 아래 백준 문제를 이 알고리즘으로 해결 가능하다.

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

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<int> arr(N);
    vector<int> lis;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (lis.empty()) {
            lis.push_back(arr[i]);
        } else if (lis.back() < arr[i]) {
            lis.push_back(arr[i]);
        } else {
            *lower_bound(lis.begin(), lis.end(), arr[i]) = arr[i];
        }
    }
    cout << lis.size();
    return 0;
}

이분 탐색으로 LIS 배열까지 - $O(NlogN)$

LIS의 크기를 $O(NlogN)$으로 구했지만 완성된 벡터는 LIS와 차이가 있었다. 실제 LIS를 구하려면 index 배열을 하나 더 두어 LIS가 최신화될 때마다 index를 저장해야 한다.

LIS가 최신화될 때마다 LIS의 index를 indices 벡터에 저장하고, 역순으로 순회하며 LIS의 index의 역순으로 해당 index가 최신화될 때의 Array 값을 ans에 저장한 후, 역순으로 출력하면 진짜 LIS가 나온다. 이 알고리즘으로 아래 백준 문제 해결이 가능하다.

가장 긴 증가하는 부분 수열 5

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<int> arr(N);
    vector<int> lis;
    vector<int> indices(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (lis.empty()) {
            lis.push_back(arr[i]);
            indices[i] = lis.size() - 1;
        } else if (lis.back() < arr[i]) {
            lis.push_back(arr[i]);
            indices[i] = lis.size() - 1;
        } else {
            auto lower_bound_it = lower_bound(lis.begin(), lis.end(), arr[i]);
            *lower_bound_it = arr[i];
            indices[i] = lower_bound_it - lis.begin();
        }
    }
    cout << lis.size() << '\n';
    vector<int> ans;
    int idx = lis.size() - 1;
    for (int i = N - 1; i >= 0; i--) {
        if (idx == indices[i]) {
            ans.push_back(arr[i]);
            idx--;
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << ' ';
    }
    return 0;
}