[C++] 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)

1. 부분 수열과 증가하는 부분 수열이란?

부분 수열

부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열을 의미한다.

만약 { 3, 2, 5, 2, 3, 1, 4 } 라는 수열이 있다면 {3}, {2}, {2, 5}, {3, 5, 3, 1} 등이 해당 수열의 부분 수열이 되며, 수열 자체도 자기 자신의 부분 수열에 포함된다.

증가하는 부분 수열

증가하는 부분 수열은 부분 수열들 중에서도 그 수가 오름차순으로 증가하는 부분 수열을 의미한다.

위에 있던 수열의 증가하는 부분 수열은 {2, 5}, {2, 3, 4} 등이 있고, 원소가 하나일 때도 증가하는 부분 수열에 포함된다.

 

이번 포스트에서 소개할 가장 긴 증가하는 부분 수열은 그 중에서도 가장 길이가 긴 것을 의미한다. 가장 긴 증가하는 부분 수열은 말이 길기 때문에 LIS라고 자주 불린다.

 

LIS는 주로 DP를 활용하여 구현하

2. LIS 구현 1 - O(N^2) 알고리즘

LIS는 주로 DP를 활용하여 구현한다.

dp[i]가 i번째 원소를 마지막으로 하는 LIS의 길이를 의미할 때,
dp[i]는 0 ~ i-1번째 원소 중 값은 arr[i]보다 작지만 가장 큰 DP 값을 가지는 원소의 DP 값에 1을 더한 값이다.

 

표를 그려보면서 예시를 들어보자. 편의를 위해 arr의 원소는 인덱스가 1부터 시작한다고 가정한다.

 

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	1

i=1

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	1	2

i=2

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	1	2	3

i=3

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	1	2	3	2

i=4

arr[3] > arr[4]이기 때문에 dp[4] = dp[2] + 1이다.

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	1	2	3	2

i=5

해당 방법은 dp[i]를 구하기 위해 순차 탐색을 진행하기 때문에 전체 시간 복잡도는 O(N^2)이 된다.

 

이를 코드로 구현하면 아래와 같다.

11053번: 가장 긴 증가하는 부분 수열

 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr = vector<int>(n+1);
    vector<int> dp = vector<int>(n+1);
    arr[0] = 0;
    dp[0] = 0;
    dp[1] = 1;

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

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

    int ret = 0;
    for (auto elem : dp) {
        if (elem > ret) ret = elem;
    }

    cout << ret << "\n";

    return 0;
}

 

2. LIS 구현 2 - O(NlogN) 알고리즘

앞선 방법에서는 dp[i]를 갱신할 때 순차 탐색으로 구현하였는데 이분 탐색을 사용하여 구현하면 시간 복잡도를 줄일 수 있다.

 

이 때는 DP 배열을 다르게 정의해야 한다.

dp[i]가 길이가 i인 증가하는 부분 수열 중 끝점의 최솟값을 의미하고 현재 탐색 중인 원소를 here이라고 할 때,

dp 배열이 비어 있거나 dp의 마지막 원소보다 here이 더 클 경우, dp 배열의 뒤에 here을 추가
그렇지 않을 경우, dp 배열에서 here의 lower_bound를 찾아 그 자리를 here로 바꾼다.

• lower_bound: 찾으려는 값 이상의 수가 처음 등장하는 위치(인덱스)

 

이번에도 표를 그리면서 이해를 해보자.

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	10

i=1

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	10	20

i=2

 

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	10	20	30

i=3

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	10	15	30

i=4

 

i=4일 때는 dp 배열이 비어 있지도 않고, here(=15)이 dp의 마지막 원소인 30보다 작다. 그리고 here의 lower_bound는 2이기 때문에 dp[2]가 15로 갱신된다.

 

i	0	1	2	3	4	5
arr[i]	0	10	20	30	15	25
dp[i]	0	10	15	25

i=5

 

비슷하게 i=5일 때 25의 lower_bound는 3이므로 dp[3]가 25가 된다.

 

이 때 가장 긴 증가하는 부분 수열의 길이는 DP 배열의 길이-1이 된다. (0번째 원소는 무시하기 때문)

DP 배열은 항상 오름차순으로 유지되기 때문에 이분 탐색을 사용할 수 있고, 이분 탐색을 이용하므로 시간 복잡도도 줄일 수 있는 것이다.

 

앞에서 풀었던 백준 11053번을 해당 방법으로 다시 풀면 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr = vector<int>(n+1);
    vector<int> dp;
    arr[0] = 0;

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

    for (int i = 1; i < n+1; ++i) {
        // 비어있거나 dp의 마지막 원소보다 here이 크다면 dp에 here을 추가
        if (dp.empty() || dp.back() < arr[i]) {
            dp.push_back(arr[i]);
        } else { // 그렇지 않다면 lower_bound를 찾아 dp 배열 갱신
            int lb = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
            dp[lb] = arr[i];
        }
    }

    cout << dp.size() << "\n";
    return 0;
}

 

LIS를 구성하는 원소들을 구하는 방법

알고리즘을 수행한 뒤 마지막에 dp에 들어있는 원소들은 LIS의 구성 요소들이 아니다. 그러므로 LIS를 구성하는 원소들을 알고 싶다면 추가적인 처리가 필요하다. 그 방법은 다음과 같다.

 

또 다른 배열 P를 만들고, P[i]에 수열의 i번째 원소가 dp 내에서 위치하는 인덱스를 저장한다.

 

#include <bits/stdc++.h>

using namespace std; 
int arr[1001], L[1001], P[1001], len, N;

void backtrace(int idx, int num) { 
    if(idx == 0) return; 
    if(P[idx] == num) { 
        backtrace(idx - 1, num - 1); 
        cout << arr[idx] << " "; 
    } else { 
        backtrace(idx - 1, num); 
    }
}

int main() { 
    ios_base::sync_with_stdio(false);
    cin >> N; 
    for(int i = 1; i <= N; ++i) { 
        cin >> arr[i]; 
        auto pos = lower_bound(L + 1, L + len + 1, arr[i]); 
        *pos = arr[i]; 
        P[i] = distance(L, pos); 
        if(pos == L + len + 1) len++;
    } 
    
    cout << len << "\n"; 
    backtrace(N, len); 
    return 0;
}

 

distance()는 벡터에서 해당 데이터가 어디에 위치하는지 가져오는 메서드이다.

 

Reference

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

 

[알고리즘] 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)