가장긴증가하는부분수열(LIS)_DP/Binary Search

가장 긴 증가하는 부분수열의 개념

부분 수열이란, 본래 수열에서 일부 숫자를 지워 만들 수 있는 수열이다. 

가장 긴 증가하는 부분 수열(LIS, Logest Increasing Subsequence)은 오름차순으로 증가하는 부분 수열 중에서 가장 긴(원소의 개수가 많은) 수열을 의미한다.

 

예를 들어, N = 7인 수열 {6, 2, 4, 3, 1, 4, 8}은 여러 부분 수열을 가진다.

- {6, 4, 1}, {6, 8}, {3, 4}, {2, 3, 4} 등은 모두 부분수열이다.

- 그 중에서 {2, 4, 8}, {4, 8}, {2, 3, 4}, {1, 4, 8} 등은 증가하는 부분 수열이다.

- 가장 긴 증가하는 부분 수열은 길이가 4인 {2, 3, 4, 8} 이다.

 

 

가장 긴 증가하는 부분 수열의 길이는 크게 두 가지 방법으로 구할 수 있다.

1) DP(동적프로그래밍)을 사용하는 O(N^2) 알고리즘

2) Binary Search(이분 탐색)을 사용하는 O(NlogN) 알고리즘 

 

 

 

DP로 LIS의 길이 구하기

dp[i] = i번째 원소로 끝나는 가장 긴 증가하는 부분 수열의 길이 라 할 때,

dp[i] = 0~i-1번째 인덱스에 있고 i번째 수보다 작은 수들에 대하여, 이 수들로 끝나는 가장 긴 증가하는 부분 수열의 길이의 최댓값+1이다. 최종적인 LIS 길이는 dp값들 중에서 가장 큰 값이므로 이를 따로 구하여 출력한다.

 

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

int N = 7;
int A[7] = {6, 2, 4, 3, 1, 4, 8};
int dp[7];

int main() {

    dp[0] = 1;
    for (int i=0; i<N; i++) {
        for (int j=0; j<i; j++) { //0~i-1 인덱스 수로 끝나는 LIS 길이 중 최댓값 구하기
            if (A[j] >= A[i]) continue;
            dp[i] = max(dp[i], dp[j]);
        }
        dp[i]++;
    }

    cout<<*max_element(dp, dp+N)<<endl;
    return 0;
}

/*output: 4*/

 

DP로 LIS의 길이를 구하는 경우, 시간 복잡도는 O(N^2)이 된다.

 

 

 

이분 탐색으로 LIS의 길이 구하기

L[i] =  길이가 i+1인 증가하는 부분 수열들에 대하여, 가장 작은 마지막 원소 이다.

배열의 원소들을 L[i]에 삽입해 나가며, 최종적으로 L[i]에 삽입된 원소들의 개수가 가장 긴 증가하는 부분 수열의 길이가 된다. 원소를 삽입할 위치를 파악하기 위해 시간 복잡도가 O(logN)인 이분탐색 함수 lower_bound()를 사용한다.

 

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

int N = 7;
int A[7] = {6, 2, 4, 3, 1, 4, 8};
int L[7];

int main() {

    int len = 0;
    for (int i=0; i<N; i++) {
        int pos = lower_bound(L, L+len, A[i])-L; //A[i]를 삽입할 수 있는 가장 왼쪽 위치 파악
        L[pos] = A[i];
        if (pos == len) len++;
    }

    cout<<len<<endl;
}

/*output: 4*/

 

이분탐색으로 LIS의 길이를 구하는 경우, 시간 복잡도는 O(NlogN)이 된다.

 

 

 

DP로 LIS 자체를 구하는 방법

pre[i] = i번째 원소 이전에 오는 원소의 인덱스 를 미리 구해놓은 뒤, 가장 긴 증가하는 부분 수열이 끝나는 지점 부터 시작하는 지점(pre[i] = -1)의 원소를 출력한다.

 

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

int N = 7;
int A[7] = {6, 2, 4, 3, 1, 4, 8};
int dp[7];
int pre[7];

void backtrace(int idx) {

    if (idx < 0) return;
    backtrace(pre[idx]);
    cout<<A[idx]<<" ";
}


int main() {

    dp[0] = 1;
    for (int i=0; i<N; i++) {
        pre[i] = -1;
        for (int j=0; j<i; j++) { //0~i-1 인덱스 수로 끝나는 LIS 길이 중 최댓값 구하기
            if (A[j] >= A[i]) continue;
            if (dp[i] < dp[j]) {
                dp[i] = dp[j];
                pre[i] = j;
            }
        }
        dp[i]++;
    }

    int idx = max_element(dp, dp+N)-dp;
    backtrace(idx);
    return 0;
}

/*output: 2 3 4 8*/

 

 

 

이분 탐색으로 LIS 자체를 구하는 방법

이분 탐색으로 구한 L 배열은 LIS의 길이 정보만 내포할 뿐, 실제의 LIS 배열은 따로 구해주어야 한다.

이 때, P[i] = i번째 원소를 배열 L에 삽입 시킨 위치 로 설정한다.

 

수열 {6, 2, 4, 3, 1, 4, 8}의 LIS을 구하기 위해 P를 채우면, int P[] = {0, 0, 1, 1, 0, 2, 3} 이 도출된다. 배열의 끝에서 부터 3, 2, 1, 0 이 최초로 등장하는 인덱스의 원소를 출력한다. 

 

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

int N = 7;
int A[7] = {6, 2, 4, 3, 1, 4, 8};
int L[7];
int P[7];

void backtrace(int idx, int num) { //P[idx]에서 숫자 num 찾기

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

int main() {

    int len = 0;
    for (int i=0; i<N; i++) {
        int pos = lower_bound(L, L+len, A[i])-L;
        L[pos] = A[i];
        P[i] = pos; //i번째 원소가 L에 삽입된 위치 저장
        if (pos == len) len++;
    }

    backtrace(N-1, len-1);
    return 0;
}

/*output: 2 3 4 8*/