DP - LIS(Longest Increasing Subsequence) c++ [컴공과고씨]

최장 증가 수열의 길이(LIS)

다음과 같은 수열이 있을 때 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분의 수열의 길이를 말함.

-> 3,2,6,4,5,1 일 경우는 

2,4,5 | 3,5,6 => 즉, 3 이다. 

이걸 구하는 알고리즘이 LIS이다.

 

Brute-force 방법으로 푼다면 

길이가 0 일때 모든 부분집합.

1일 때 2일 때 ... 쭉 불가능 할 때 까지 가는 것이다.

이 경우 같은 경우 부분집합의 총 개수가 2^N이기 때문에 O(2^n)이 나오게 된다.

 

Dynamic programming(DP)

숫자열 - a,b,c,d,e .... 

LIS[i] : a,b,c,d,e에서 가장 긴 부분 수열의 길이라 하면

1번 : LIS(i)가 i번째 원소를 포함하지 않는다면, LIS(i) = LIS(i-1)이다.

2번 : LIS(i)가 i번째 원소를 포함한다면?

i번째 원소보다 작은 원소를 그 전에 있던 원소에서 찾는다. 

그 전에 있던 원소를 찾기 위해서는 모두 검색을 해야만 찾을 수 있음.

그 중 최대값을 찾아 1증가시켜서 LIS(i)에 저장해주면 된다.

시간 복잡도는 O(N^2)이 됩니다. 

ex) {3,2,6,4,5,1}

dp(1) = 1

dp(2) = 1

dp(3) = {3,6} -> 2

dp(4) = {3,4} -> 2

dp(5) = {3,4,5} = 3

dp(6) = 1

 

코드로 푼다면 이런식이 될 것이다.

int last = 0;
int len = 1;
int prev[10], dp[10];
for(int i =0; i<n; i++){
    dp[i] = 1;
    prev[i] = -1; 
    
    for(int j=0; j<i; j++){
        if(a[j] > a[i])
            continue;
        
        if(dp[i] < dp[j]+1){
            dp[i] = dp[j]+1;
            prev[i] = j;
            if(len < dp[i]){
                last = i;
                len = dp[i];
            }
        }
    }
}
void PrintArray(int pos){
    if(pos<0)
        return;
    PrintArray(prev[pos]);
    cout << a[pos] << " ";
}
void PrintArray(int pos){
    int idx = pos;
    for(int i = 0; idx >= 0; i++){
        ans[i] = idx;
        idx = prev[idx];
    }
    for(int i = dp[n-1]-1; i>=0; i--)
        cout << a[ans[i]] << " ";
}