[자료구조 및 알고리즘] 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)

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

가장 긴 증가하는 부분 수열은 주어진 배열에서 순서를 유지한 채로 길이가 가장 긴 증가하는 부분 수열을 찾는 문제이다. 예를 들면 배열 [10, 9, 2, 5, 3, 7, 101, 18]이 주어지면 이 배열에서 길이가 가장 긴 증가하는 부분 수열은 [2, 3, 7, 101]이며 길이는 4이다. 간단해 보이는데, 접근 방법을 모르면 어려운 유형이므로 기록한다.

 

해결 방법

해결 방법은 2가지가 있다. 동적 계획법을 이용한 방법과 이분 탐색을 활용한 방법이다.

 

동적 계획법, 시간복잡도 O(N^2)

#include <iostream>

using namespace std;
int n,a[1003],cnt[1003],res;

int main() {
    cin >> n;
    fill(cnt, cnt + 1003, 1); // 자기 자신 1개를 채워주는 과정
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
        	// a[i]가 a[j]보다 큰 경우 and
            // a[j]를 포함한 부분 수열의 길이 cnt[j]에 현재 원소 a[i]를 추가한 길이 cnt[j] + 1이
            // cnt[i]보다 큰 경우 확인
            if(a[i] > a[j] && cnt[i] < cnt[j] + 1) { 
                cnt[i] = cnt[j] + 1; 두 조건이 참일 때 갱신
            }
        }
        res = max(res, cnt[i]); // 최대 길이 갱신
    }
    cout << res << '\n';
    return 0;
}

1. 각 원소 a[i]에 대해 이전 원소 a[j]들과 비교하여 증가하는 부분 수열을 찾고

2. 현재 원소 a[i]를 끝으로 하는 가장 긴 부분 수열의 길이를 갱신

3. 모든 원소를 순회하면서 각 원소를 끝으로 하는 부분 수열의 최대 길이를 계산하고, 가장 긴 길이를 res에 저장

 

이분 탐색, 시간복잡도 O(NlogN)

#include <iostream>
#include <algorithm> // lower_bound 사용

using namespace std;
int n,a[100003],res,num;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> num;
        auto k = lower_bound(a, a + res, num); // num보다 크거나 같은 첫번쨰 원소 위치 탐색
        if(*k == 0) res++; // 찾은 값에 0이 저장되어 있다면 길이 증가
        *k = num; // lower_bound로 찾은 주소에 입력 받은 값 저장(가장 긴 수열을 찾기 위해)
    }
    cout << res << '\n';
    return 0;
}

1. 값을 입력 받고 lower_bound를 사용하여 현재 숫자가 배열 a에서 들어갈 위치를 탐색

2. 찾은 위치의 값이 0인 경우(값이 할당되지 않은 경우) res를 증가시켜 LIS 길이를 늘림

3. 값 업데이트

 

이분 탐색을 이용하는 알고리즘을 사용하면 길이는 찾을 수 있는데, 원본 배열을 찾을 수는 없다. 원본 배열을 찾기 위해서는 또 다른 배열을 만들어서 lower_bound로 찾은 위치와 값을 저장한 후, 길이와 비교해서 찾아낼 수 있다.