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

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

최장 증가 부분 수열, Longest Increasing Subseqeunce는 어떠한 수열의 부분 수열중 오름차순으로 증가하는 가장 긴 수열을 의미한다. (이때 각 원소는 연속할 필요는 없다.)

아래의 예시 수열을 보자.

[ 7, 3, 5, 2, 7, 4, 8, 2]

이 수열에서 증가하는 순열에는 [2, 4], [2, 4, 8], [3, 5] 등 다양한 것이 있지만 LIS는 [3, 5, 7, 8]이 된다.

📝 LIS를 구해보자

LIS를 구하는 방법에는 동적 계획법(DP)와 이분탐색으로 크게 두가지의 방법이 있다. DP는 $O(n^2)$의 시간복잡도를 보이며, 이분탐색으로 구현하게 되면 $O(n\log{n})$의 시간복잡도가 나타난다.

1) 동적 계획법 (Dynamic Programming)으로 구현하기

a 배열의 i 번쨰 인덱스에서 끝나는 LIS 길이를 length[i]라 하자.

이때 i보다 작은 인덱스 j에 대해 a[i]가 a[j]보다 크다면 length[i]는 length[k]+1의 최댓값이라 할 수 있다. 

 

이해를 돕기 위해 위쪽의 배열을 예시로 들어보자.

• 인덱스 0에서 종료되는 LIS의 길이는 1이다. (7)
• 인덱스 1에서 종료되는 LIS의 길이는 1이다. (3)
• 인덱스 2에서 종료되는 LIS의 길이는 2이다. (3, 5)
• 인덱스 3에서 종료되는 LIS의 길이는 1이다. (2)
• 인덱스 4에서 종료되는 LIS의 길이는 3이다 (3, 5, 7)
• ...

이를 C++로는 다음과 같이 구현할 수 있다.

#include <iostream>

using namespace std;

int a[100], length[100], n;

void dpFunc() {
    int res=0;
    for(int i=0; i<n; i++) {
        length[i]=1;
        for(int j=0; j<i; j++)
            if(a[i]>a[j]) length[i]=max(length[i], length[j]+1);
        if(length[i]>res) res=length[i];
    }
    cout << res;
}

int main(void) {
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    dpFunc();
    return 0;
}

2) 이분탐색으로 구현하기

LIS의 형태를 유지하기 위해 배열의 인덱스를 하나씩 살펴보면서 숫자가 들어갈 위치를 이분탐색으로 찾아서 넣는다.

C++로는 다음과 같이 구현할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int a[100], n;

int binary_search(vector<int> lis, int start, int end, int element) {
    while (start < end) {
        int mid = (start + end) / 2;
        if (element > lis[mid]) start = mid + 1;
        else end = mid;
    }
    return end;
}
 
int LIS_BS() {
    int ret = 0;
    vector<int> lis;
    lis.push_back(a[0]);
    for (int i = 1; i < n; i++) {
        if (a[i] > lis.back()) {
            lis.push_back(a[i]);
            ret = lis.size() - 1;
        }
        int pos = binary_search(lis, 0, ret, a[i]);
        lis[pos] = a[i];
    }
    return ret + 1;
}
int main(void) {
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    cout << LIS_BS();
    return 0;
}

출처 / 참고 자료

https://chanhuiseok.github.io/posts/algo-49/

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

https://4legs-study.tistory.com/106

최장 증가 수열 (LIS, Longest Increasing Subsequence)