[Algorithm] 최장 증가 부분 수열(LIS)

DP 문제인 LIS 문제를 풀기 위해 LIS 알고리즘을 공부했습니다.

제가 공부한 내용을 바탕으로 작성했습니다.

잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다!

 

 

최장 증가 부분 수열(LIS)이란?

 

수열이 주어지고 해당 수열에서 몇개의 수를 제거했을 때 부분 수열을 만들 수 있습니다.

부분 수열 중에서 오름 차순으로 정렬되고, 길이가 가장 긴 부분 수열을 최장 증가 부분 수열(LIS)이라고 합니다.

 

그렇다면 이해를 위해 예를 들어보도록 하겠습니다.

{3, 5, 7, 9, 2, 1, 4, 8} 수열이 있습니다.

몇개의 수를 제거하여 부분 수열을 만들면

{3, 5, 7, 9, 2}

{5, 7, 9}

{3, 5, 7, 8}

{3, 5, 7, 9}

등을 만들 수 있습니다.

 

✔ {3, 5, 7, 9, 2}의 경우

부분 수열이지만 일부 원소만 오름 차순으로 정렬되어 있습니다.

 

✔ {5, 7, 9}의 경우

부분 수열이고 전체 원소가 오름 차순으로 정렬되어 있습니다. 그리고 부분 수열의 길이는 3입니다.

 

✔ {3, 5, 7, 8}과 {3, 5, 7, 9}의 경우

부분 수열이고 전체 원소가 오름 차순으로 정렬되어 있습니다. 그리고 부분 수열의 길이는 4입니다.

 

그래서 위 수열에서 최장 증가 부분 수열은 길이가 4인 {3, 5, 7, 8}과 {3, 5, 7, 9} 입니다.

최장 증가 부분 수열은 여러개 존재할 수 있습니다.

 

 

최장 증가 부분 수열(LIS) 알고리즘 구현

 

 

최장 증가 부분 수열(LIS)에 대한 개념도 익혔으니 코드로 구현해봅시다.

 

 

방법 1. O(n^2) - DP 이용

 

설명하기에 앞서, 방법 1은 입력 범위가 10,000 아래일 때만 사용해야합니다.

입력 범위가 10,000 을 넘어서면 시간 초과가 발생합니다.

 

위 그림과 같이 수열의 한 원소인 6을 마지막 값으로 갖는 최장 증가 부분 수열을 생각해보면

6 이전의 원소들은 6보다 작아야합니다.

 

따라서 6의 이전의 원소들{1, 3, 2, 5} 중 값이 6보다 작은 원소들에 대해

각각의 원소들을 마지막으로 값으로 갖는 최장 증가 부분 수열(LIS)을 알면 6을 마지막 값으로 갖는 최장 증가 부분 수열(LIS)을 구할 수 있습니다.

 

6 이전의 수열 {1, 3, 2, 5} 수열에서 각각의 원소를 마지막 값으로 갖는 최장 증가 부분 수열(LIS)을 구하면

1을 마지막 값으로 갖는 최장 증가 부분 수열 : 1 {1}

3을 마지막 값으로 갖는 증가 부분 수열 : 2 {1, 3}

2를 마지막 값으로 갖는 최장 증가 부분 수열 : 2 {1, 2}

5를 마지막 값으로 갖는 최장 증가 부분 수열 : 3 {1, 3, 5} 또는 {1, 2, 5}

 

이들 중 가장 길이가 긴 {1, 3, 5} 또는 {1, 2, 5} 에

현재 수인 6을 추가한 {1, 3, 5, 6} 또는 {1, 2, 5, 6} 이 6을 마지막 값으로 갖는 최장 증가 부분 수열이 됩니다.

 

즉 이전 원소의 값이 현재 원소보다 작고,

이전 원소를 마지막 값으로 갖는 최장 증가 부분 수열 중 가장 큰 값에 + 1 한것이

현재 원소가 마지막 값으로 갖는 최장 증가 부분 수열입니다.

 

따라서 dp[i] = i번째 원소를 마지막 값으로 갖는 최장 증가 부분 수열로 정의할 수 있습니다.

 

 

코드로 구현하면 아래와 같습니다. (주석 포함)

void lengthOfLIS(vector<int>& A) {
    vector<int> dp(N, 1); // 주어진 수열 크기만큼 초기화
    // LIS가 최소 1이상이기 때문에 1로 초기화
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < i; ++j) {
        // i번째 이전 모든 원소들에 대해 해당 원소를 마지막 값으로 갖는 LIS와 값을 확인해야함
        
            // 조건 1. 현재 값(A[i])이 이전 값(A[j])보다 커야함
            if(A[i] > A[j]) {
            	// dp[j] + 1 : 이전 원소의 LIS에 현재 원소를 붙인 LIS
            	dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
}

 

 

 

방법 2. O(nlogn) - lower_bound 이용(이진 탐색)

 

 

🌟 중요 🌟

최장 증가 부분 수열(LIS)를 만들기 위해서 마지막 원소가 가능한 작을수록 더 긴 최장 증가 부분 수열(LIS)를 만들 수 있다는 것입니다.

그러므로 원소가 들어올 때, 만약 현재 만들어진 최장 증가 부분 수열(LIS)의 마지막 원소보다 작은 경우, 이진 탐색(lower_bound)으로 들어갈 위치를 찾은 후(nlongn) 원소를 대체합니다.

 

 

그렇다면 예시를 들어보도록 하겠습니다.

수열 {1, 3, 5, 8, 6, 7}이 있을 때 6까지 탐색을 했을 때 만들어지는 최장 증가 부분 수열(LIS)는

{1, 3, 5, 6}

{1, 3, 5, 8}

2가지인데, 더 긴 최장 증가 부분 수열(LIS)를 만들기 위해서는 {1, 3, 5, 8}보단 {1, 3, 5, 6}이 적합합니다.

마지막 7의 원소가 들어올 때 {1, 3, 5, 8}로는 만들 수 없고 {1, 3, 5, 6}의 경우에만 {1, 3, 5, 6, 7} 로 만들 수 있습니다.

 

 

{1, 3, 5, 8, 6, 7}

1. {1}

2. {1, 3} ➜ 3이 1보다 크기 때문에 뒤에 추가

3. {1, 3, 5}  ➜ 5가 3보다 크기 때문에 뒤에 추가

4. {1, 3, 5, 8} ➜ 8이 5보다 크기 때문에 뒤에 추가

5. {1, 3, 5, 6} ➜ 6이 8보다 작기 때문에 8이 6으로 대체됨

6. {1, 3, 5, 6, 7} ➜ 7이 6보다 크기 때문에 뒤에 추가

 

이 알고리즘을 통해 길이를 구할 수 있습니다.

 

 

코드로 구현하면 아래와 같습니다. (주석 포함)

#include <bits/stdc++.h>
using namespace std;

vector<int> LIS;

int main(void) {
    vector<int> arr = {1, 3, 5, 8, 6, 7};

    for(int element : arr) {
        if(LIS.empty()) {
            // 초기
            LIS.emplace_back(element);
        } else {
            if(LIS.back() < element) {
                // 뒤 원소보다 큰 경우 추가
                LIS.emplace_back(element);
            } else {
                // 뒤 원소보다 작기 때문에 들어갈 위치를 찾는다.
                // element 값보다 같거나 큰 값이 처음 나오는 위치를 리턴한다.
                auto location = lower_bound(LIS.begin(), LIS.end(), element);
                // 값을 변경한다.
                *location = element;
            }
        }
    }
    cout << LIS.size();
    return 0;
}

 

 

 

위 방법 2가지는 길이를 구하는 데만 초점이 맞추어져 있는 알고리즘 입니다.

만약 길이가 아닌 최장 증가 부분 수열을 구하라고 한다면 위 알고리즘에서 약간의 코드가 더 추가됩니다.

 

바로 아래에서 이어서 작성해보도록 하겠습니다.

 

 

O(nlogn) - 최장 증가 부분 수열 구하기

 

 

방법 2 에서 약간의 코드(?)가 추가되었습니다.

 

vector<pair<int, int>> backtrace 변수를 만들었습니다.

위 변수는 수열의 원소가 최장 증가 부분 수열(LIS) vector에 들어가는 인덱스와 원소의 값을 저장합니다.

 

그리고 마지막 원소부터 LIS 길이를 감소시키면서 LIS 길이와 원소의 인덱스가 같은 경우에만 따로 다른 vector 변수에 저장합니다.

 

예를 들어보도록 하겠습니다.

{1, 4, 5, 3} 수열

1. {1}

2. {1, 4}

3. {1, 4, 5}

4. {1, 3, 5}

이므로 1 = 0번째 인덱스 , 4 = 1번째 인덱스, 5 = 2번째 인덱스, 3 =  1번째 인덱스

즉 backtrace vector는 {{0, 1}, {1, 4}, {2, 5}, {1, 3}} 이 됩니다.

 

그래서 현재 LIS 길이는 3인데 0번째 인덱스부터 카운트 했으므로 -1을 해줌으로서 2부터 시작합니다.

뒤에서부터 길이 2와 인덱스가 같은 원소는 5이고 찾았으므로 길이를 -1 합니다.

그다음 길이 1과 인덱스가 같은 원소는 4이고 찾았으므로 길이를 -1 합니다.

그다음 길이 0과 인덱스가 같은 원소는 1이고 찾았으므로 길이를 -1 합니다.

 

따라서 {5, 4, 1}을 다시 오름 차순 정렬을 하게 되면 {1, 4, 5}로 최장 증가 부분 수열을 구할 수 있습니다.

코드를 보면서 이해하면 더 쉽습니다.

 

 

코드로 구현하면 아래와 같습니다. (주석 포함)

#include <bits/stdc++.h>
using namespace std;

vector<int> LIS;
vector<int> ans;
vector<pair<int, int>> backtrace; // 인덱스, 값

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N; // 수열의 크기
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        if(LIS.empty()) {
            LIS.emplace_back(n);
            backtrace.push_back({LIS.size() - 1, n});
        } else {
            if(LIS.back() < n) {
                LIS.emplace_back(n);
                backtrace.push_back({LIS.size() - 1, n});
            } else {
                auto location = lower_bound(LIS.begin(), LIS.end(), n);
                LIS[location - LIS.begin()] = n;
                backtrace.push_back({location - LIS.begin(), n});
            }
        }
    }
    cout << LIS.size() << '\n';
    int len = LIS.size() - 1; // 0번째 인덱스부터 시작해서 -1함
    for(int i = N -1; i >= 0; --i) {
        if(backtrace[i].first == len) {
            len -= 1;
            ans.emplace_back(backtrace[i].second);
        }
    }

    sort(ans.begin(), ans.end()); // 역순으로 저장되었기 때문에 오름 차순 정렬
    for(int element : ans) {
        cout << element << ' ';
    }
   
    return 0;
}