[알고리즘] LIS(최장 증가 부분 수열)

LIS(Longest Increasing Subsequence)란?

주어진 수열에서 순서를 유지하며 크기가 증가하는 부분 수열 중 가장 긴 것을 의미합니다.
아래와 같은 수열이 있습니다.

10

20

10

30

20

50

이 수열의 LIS는 아래와 같고 크기는 4입니다.

10

20

30

50

---

LIS 구현 방법

1. DP를 이용한 LIS 구현

LIS는 기본적으로 DP를 통해 구현합니다. DP[i]에는 i번째 원소를 마지막으로 하는 LIS의 길이를 저장합니다.
DP의 점화식은 다음과 같습니다.

for(int i = 0; i < n; i++){
    dp[i] = 1;
    for(int j = 0; j < i; j++){
        if(arr[j] < arr[i]){
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

DP 배열을 모두 순회하며, i번째 원소를 LIS에 포함시키려면, 그 앞에 있는 원소 중 arr[i]보다 작은 값을 찾아야 합니다. 그런 j를 모두 확인해서, dp[j]값이 가장 큰 것을 선택하고, 거기에 1을 더해 현재 원소를 추가하는 것입니다.
 
전체 코드를 보겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    vector<int> dp(n, 1);

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

    int result = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        result = max(result, dp[i]);
    }

    cout << result << '\n';
    return 0;
}

DP를 이용한 방법의 시간복잡도는 O( N²), 공간복잡도는 O( N )입니다.

2. 이분 탐색을 이용한 LIS 구현

Lower Bound를 통해 LIS벡터의 증가 수열을 유지하고, 갱신하며 최적화하는 방법입니다.
 간단히 설명하면 LIS 배열을 항상 오름차순으로 유지하며, LIS[i]는 크기가 i + 1인 가장 작은 값으로 갱신하는 방법입니다. 각 원소를 처리할 때는 현재의 수가 LIS 배열의 마지막 요소보다 크다면(arr[i] > LIS[size - 1]) LIS 배열에 push_back을 해서 크기를 증가시킵니다. 그렇지 않다면 Lower Bound로 들어갈 수 있는 위치를 찾아 교체합니다.

LIS를 만들 때, 같은 크기라면 끝 값이 작을수록 유리합니다. 왜냐하면 뒤에 올 수 있는 후보가 더 많아지기 때문입니다.
 
예시를 들겠습니다.
 수열 : [1, 5, 2, 3, 4]
이 수열이 있을 때
 
 부분 수열 : [1, 5, ?] : 5보다 큰 수만 올 수 있음
 부분 수열 : [1, 2, ?] : 2보다 큰 수 가능
이 예시를 보더라도 LIS[1]을 2로 갱신하였을 때 더 크기가 큰 LIS를 구할 수 있습니다.
 
코드를 확인하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    vector<int> lis;

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

    for (int i = 0; i < n; i++) {
        auto pos = lower_bound(lis.begin(), lis.end(), arr[i]);
        if (pos == lis.end()) {
            lis.push_back(arr[i]);
        } else {
            *pos = arr[i];
        }
    }

    cout << lis.size() << '\n';
    return 0;
}

 
이분 탐색 직접 구현

#include <iostream>
#include <vector>
using namespace std;

int lower_bound(vector<int>& lis, int tar) {
    int s = 0, e = lis.size();
    while (s < e) {
        int mid = s + (e - s) / 2;
        if (lis[mid] < tar) {
            s = mid + 1;
        }
        else {
            e = mid;
        }
    }
    return s;
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    vector<int> lis;

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

    for (int i = 0; i < n; i++) {        
        if (arr[i] > *lis.rbegin()) {
            lis.push_back(arr[i]);
        }
        else {
            int pos = lower_bound(lis, arr[i]);
            lis[pos] = arr[i];
        }
    }

    cout << lis.size() << '\n';
    return 0;
}

이분 탐색을 이용한 구현의 시간복잡도는 O( N log N )입니다.
 
 한 가지 유의할 점이 있습니다. 이분 탐색을 이용한 구현에서 LIS 배열의 크기는 LIS의 길이를 나타내지만, 벡터 자체가 실제 LIS를 나타내는 것은 아닙니다. 각 크기별 최소 끝 값만을 저장하기 때문입니다. 실제 LIS 수열을 복원하려면 추가 정보를 기록해야 합니다.

3. 이분 탐색을 이용한 LIS 구현 + LIS 수열 복원

LIS의 크기를 저장해두는 배열을 만든 후 역추적하여 LIS 수열을 구할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    vector<int> dp(n);
    vector<int> res(n);
    vector<int> lis;

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

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

    int tmp = lis.size() - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (dp[i] == tmp) {
            res[tmp--] = arr[i];
        }
    }

    cout << lis.size() << '\n';
    for (int x : res) {
        cout << x << ' ';
    }
    return 0;
}

---

관련 문제

https://www.acmicpc.net/problem/11053
https://www.acmicpc.net/problem/11054
https://www.acmicpc.net/problem/14003