Longest Increasing Subsequence (LIS)

LIS

최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 수열에서 몇몇 숫자를 순서를 유지한 채로 선택해 만들 수 있는 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 백준 11053번 문제를 보면, 다음과 같은 수열이 주어졌을 때,

\[ A = \{10, 20, 10, 30, 20, 50\} \]

이 수열에서 만들 수 있는 증가하는 부분 수열은 (10), (10, 20), (10, 30), (10, 20, 50) 등 여러 가지가 있지만, 그 중 가장 긴 부분 수열은 (10, 20, 30, 50)으로 길이는 4입니다. 따라서 이 수열의 LIS의 길이는 4가 됩니다. 위 문제에서는 LIS의 길이만 구하는 것이 목표였으므로 정확한 수열은 몰라도 괜찮습니다. 일반적으로 LIS는 길이만 구하면 되지만 어려운 문제에서는 정확한 수열을 요구하기도 합니다. 이것을 역추적 또는 복원이라고 합니다. 이 글에서는 LIS의 길이를 구하는 2가지 방법과 역추적에 대해서 설명하겠습니다.

DP

LIS를 구하는 가장 직관적인 방법은 동적 계획법(DP)을 사용하는 것입니다. 길이가 \( N \)인 수열 \( A \)가 주어졌을 때, \( \text{dp}[i] \)를 \( A[i] \)를 마지막 원소로 가지는 LIS의 길이라고 정의합니다. 그러면 다음과 같은 방법으로 \( \text{dp} \) 배열을 채울 수 있습니다.

dp 배열을 모두 1로 초기화합니다. 각 원소가 자기 자신만으로 이루어진 부분 수열이 될 수 있기 때문입니다.
dp[i]는 자신보다 앞에 있는 원소 중 A[i]보다 작은 원소 A[j]에 대해 dp[j] + 1으로 생각할 수 있습니다. 따라서 i보다 작은 모든 j에 대해 A[j] < A[i]인 경우에 대해 dp[j] + 1의 최댓값으로 dp[i]를 갱신합니다.
최종적으로 dp 배열의 최댓값이 LIS의 길이가 됩니다.

점화식으로 나타내면 다음과 같습니다.

\[ \text{dp}[i] = \max_{0 \leq j < i,\,\, A[j] < A[i]} (\text{dp}[j] + 1) \]

위 문제를 이 방법으로 풀어보겠습니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int dp[n];
    fill(dp, dp + n, 1);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[i] > a[j])
                dp[i] = max(dp[i], dp[j] + 1);

    int ans = *max_element(dp, dp + n);
    cout << ans;
}

굉장히 간단하게 구현할 수 있습니다. 하지만 이 방법은 \( O(N^2) \)의 시간복잡도를 가집니다. 이 문제에서는 \( N \)의 최대값이 1,000이기 때문에 이 방법으로도 충분히 통과할 수 있지만, \( N \)이 더 커지면 사용할 수 없습니다. 다음 절에서는 더 효율적인 방법을 설명하겠습니다.

이분 탐색

12015번 문제는 앞의 문제와 동일하지만 수열의 최대 길이가 1,000,000으로 매우 큽니다. 앞에서 살펴본 dp를 사용하는 방법은 사용할 수 없습니다. 그래서 이분 탐색을 사용해서 LIS의 길이를 구하는 방법을 사용합니다. 이 방법은 직관적으로는 이해하기 어려울 수 있습니다. 그래서 일단 결론을 먼저 설명하고 왜 이게 가능한지는 뒤에서 설명하겠습니다. 이 방법은 다음과 같은 순서로 이루어집니다.

빈 배열 lis를 만듭니다. lis 배열은 증가하는 수열이 되도록 유지합니다. 즉, 마지막 원소가 가장 큰 값을 가집니다.
수열의 각 원소 x에 대해 다음을 수행합니다.
- x가 가장 크다면(lis[-1] < x), lis의 마지막에 x를 추가합니다.
- 그렇지 않다면, lis에서 x 이상인 원소 중 가장 작은 원소를 x로 교체합니다. 이때 이분 탐색을 사용해 얻은 인덱스에 x를 대입하는 방식으로 구현할 수 있습니다.
최종적으로 lis 배열의 길이가 LIS의 길이가 됩니다.

말로는 조금 이해하기 어려우니 예시를 들어보겠습니다. 다음과 같은 수열이 있습니다.

\[ A = [10, 20, 10, 30, 20, 50] \]

x	lis	설명
10	[10]	lis가 비어있으므로 10을 추가
20	[10, 20]	20이 가장 크므로 추가
10	[10, 20]	10 이상인 원소 중 가장 작은 원소는 10이므로 교체
30	[10, 20, 30]	30이 가장 크므로 추가
20	[10, 20, 30]	20 이상인 원소 중 가장 작은 원소는 20이므로 교체
50	[10, 20, 30, 50]	50이 가장 크므로 추가

최종적으로 lis 배열은 [10, 20, 30, 50]이 되고, 길이는 4가 됩니다. 여기서 주의할 점은 lis 배열이 실제 LIS를 나타내지 않는다는 것입니다. 지금은 우연히 실제 LIS와 동일한 배열이 되었지만, 값의 순서를 바꾸면서 삽입하기 때문에 실제 LIS와는 다를 수 있습니다. 하지만 lis 배열의 길이는 항상 LIS의 길이와 같다는 것이 이 방법의 핵심입니다. 이 방법을 사용하면 \( O(N \log N) \)의 시간복잡도로 LIS의 길이를 구할 수 있습니다. 다시 한번 강조하지만 LIS가 아니라 LIS의 길이를 구하는 방법입니다.

방법적으로는 굉장히 간단합니다. 하지만, 여기까지 설명을 들었을 때 이해되지 않는 부분이 있을 것입니다. 지금부터 그 부분에 대해 설명하겠습니다.

우선, DP를 사용하는 방법은 가능한 모든 부분 수열을 고려하는 방식입니다. 반면, 이분 탐색을 사용하는 방법은 부분 수열의 후보군을 유지하는 방식입니다. lis 배열은 길이가 \( k \)인 증가 부분 수열이 존재할 수 있는지를 나타냅니다. 조금 더 명확하게 설명하면 lis[k]는 길이가 \( k+1 \)인 증가 부분 수열 중 마지막 원소의 값이 최소인 부분 수열의 마지막 원소를 나타냅니다. 이 정의대로라면 lis 배열은 찾고자 하는 답과 같아집니다. 왜냐하면, lis 배열의 길이가 \( L \)이라면 길이가 \( L \)인 증가 부분 수열이 존재한다는 뜻이고, 길이가 \( L+1 \)인 증가 부분 수열은 존재하지 않는다는 뜻이기 때문입니다. 이 방식이 성립하기 위해서는 lis 배열의 정의가 항상 유지되어야 합니다.

이분 탐색을 사용해 lis 배열을 갱신하는 것은 lis 배열의 정의를 유지하는 방식입니다. 새로운 원소 x가 들어왔을 때, 이분 탐색을 통해 찾은 위치가 \( k \)라고 합시다. lis[k] = x로 갱신하는 것은 길이가 \( k + 1 \)인 증가 부분 수열 중 마지막이 가장 작은 부분 수열의 마지막 원소가 x라는 의미입니다. 이는 lis 배열의 정의를 만족합니다. 만약 x가 lis 배열의 마지막 원소보다 크다면, 이는 길이가 len(lis) + 1인 증가 부분 수열이 존재한다는 의미이므로, lis 배열에 x를 추가해 갱신합니다.

이 내용을 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> lis;
    for (int i = 0; i < n; i++) {
        if (lis.empty() || lis.back() < a[i])
            lis.push_back(a[i]);
        else {
            int pos = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
            lis[pos] = a[i];
        }
    }

    cout << lis.size();
}

LIS 역추적

LIS의 길이만 구하는 것이 아니라 실제 수열을 구해야 하는 경우도 있습니다. 역추적 파트는 난이도가 높기 때문에 나중에 다시 돌아오셔도 괜찮습니다. DP를 사용하면 역추적을 비교적 쉽게 구현할 수 있습니다. 앞서 DP에서는 dp[i]가 A[i]를 마지막 원소로 가지는 LIS의 길이라고 정의했습니다. 여기에 추가로 prev[i]를 LIS에서 A[i]의 바로 앞에 오는 원소의 인덱스라고 정의합니다. 그럼 다음과 같이 코드를 수정해야 합니다(DP는 파이썬 코드는 생략하겠습니다).

int a[n];
int dp[n];
int prev[n];
fill(dp, dp + n, 1);
fill(prev, prev + n, -1);

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

이제 prev 배열을 사용해 역추적을 할 수 있습니다. 우선 dp 배열에서 최댓값의 인덱스를 찾습니다. 그 인덱스부터 prev 배열을 따라가면서 수열을 복원할 수 있습니다.

vector<int> lis;

while (idx != -1) {
    lis.push_back(a[idx]);
    idx = prev[idx];
}

reverse(lis.begin(), lis.end());

이 방법에 대한 연습문제는 14002번문제가 있습니다. 하지만 이 방법은 결국 \( O(N^2) \)의 시간복잡도를 가지기 때문에, 앞서 설명한 이분 탐색을 사용하는 방법으로 역추적을 구현해야 합니다.

14003번 문제는 LIS의 길이를 구하는 것뿐 아니라 실제 수열도 구해야 합니다. 이분 탐색을 사용하는 방법에 역추적을 구현해야 시간복잡도를 맞출 수 있습니다. 이를 위해서는 약간의 변형이 필요합니다. 우선, lis 배열을 유지하는 것 외에도 pos 배열과 parent 배열을 만들어야 합니다.

lis[k] : 길이가 k + 1인 LIS의 최소 끝값
pos[k] : 그 끝값의 실제 인덱스
parent[i] : LIS에서 A[i]의 바로 앞에 오는 원소의 인덱스

DP와 사실상 거의 동일한 방식입니다. lis 배열에 값만을 저장하기 때문에 위치를 저장하는 pos 배열이 추가되었습니다. 이제 저 세 가지 배열을 사용하려면 다음과 같이 코드를 수정해야 합니다.

vector<int> lis;
vector<int> pos;
int parent[n];
fill(parent, parent + n, -1);

for (int i = 0; i < n; i++) {
  int x = a[i];
  int idx = lower_bound(lis.begin(), lis.end(), x) - lis.begin();

  if (idx == lis.size()) {
      lis.push_back(x);
      pos.push_back(i);
  } else {
      lis[idx] = x;
      pos[idx] = i;
  }

  if (idx > 0)
      parent[i] = pos[idx - 1];
}

제일 마지막에 추가하는 경우는 단순하게 추가하면 되고, 그렇지 않은 경우는 해당 위치를 갱신해 주었습니다. 제일 처음 원소가 아닌 경우에는 parent 배열도 갱신해 주었습니다. 이제 역추적을 해서 실제 수열을 구하는 단계입니다. 단순히 pos 배열의 마지막 원소부터 parent 배열을 따라가면 됩니다.

int cur = pos.back();
vector<int> ans;

while (cur != -1) {
    ans.push_back(a[cur]);
    cur = parent[cur];
}

reverse(ans.begin(), ans.end());

실제로는 이렇게 구한 LIS 말고도 다른 LIS가 존재할 수 있지만 길이는 동일합니다. 대부분의 경우 아무 LIS나 구해도 상관없기 때문에 이 방법을 가장 많이 사용합니다. 아래는 위 문제에 대한 정답 코드입니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> lis;
    vector<int> pos;
    int parent[n];
    fill(parent, parent + n, -1);

    for (int i = 0; i < n; i++) {
        int x = a[i];
        int idx = lower_bound(lis.begin(), lis.end(), x) - lis.begin();

        if (idx == lis.size()) {
            lis.push_back(x);
            pos.push_back(i);
        } else {
            lis[idx] = x;
            pos[idx] = i;
        }

        if (idx > 0)
            parent[i] = pos[idx - 1];
    }

    int cur = pos.back();
    vector<int> ans;

    while (cur != -1) {
        ans.push_back(a[cur]);
        cur = parent[cur];
    }

    reverse(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
}