BOJ 11053, 가장 긴 증가하는 부분 수열

주어진 수열에서, 가장 긴 증가하는 부분 수열을 구하는 문제입니다.

 알고리즘 문제를 많이 접해 보지 못했던 사람들은, 이 문제를 보면 이걸 다이나믹 프로그래밍 풀어야지 하는 생각을 한번에 떠올리기란 쉽지 않습니다.

보통 이러한 문제는 모든 경우의 수를 다 따져볼 수 있는 방법으로부터 접근하곤 합니다.

예제를 볼까요?

예제로 주어진 수열의 길이는 6이고, 주어진 수열은

{10, 20, 10, 30, 20, 50} 입니다.

이 수열에서 존재하는 부분 수열의 개수는 아무것도 없는 수열(공수열이라고 하겠습니다.)을 제외하고 

6C0 + 6C1 + 6C2 + 6C3 + 6C4 + 6C5 + 6C6으로 이항정리에 의해 2^5-1 = 31개입니다. Brutforce로 해결하면, 총 2의 n-1승개의 부분수열이 존재하고, 각 수열의 증가 판정 및 최대 증가 길이를 측정하는데 O(n)의 시간이 걸리니, 이 문제를 해결하기 위해선 O( n * 2^n)의 시간이 걸립니다.

n의 범위가 1000이니 BruteForce로 이 문제를 해결하기엔 턱없이 부족합니다.

하지만, Dynamic Programming을 사용하면 이 시간복잡도를 O(n^2)까지 줄일 수 있습니다.

어떻게 줄일 수 있을까요?

우리가 해결 해야하는 문제를 봅시다.

문제 : 길이가 N인 수열의, 가장 긴 증가하는 부분 수열의 길이를 구하는 것.

이 문제는 다음과 같이 나눌 수 있습니다.

= 길이가 (N-1)인 수열의 가장 긴 증가하는 부분 수열의 길이 + (맨 뒤의 원소가 증가하면 +1, 아니면 +0)

즉, 처음부터 쭉 시작해서, 길이가 A인 지점까지 가장 긴 증가하는 수열의 길이를 구하는데, 만약 이 값을 모른다면 직접 다시 구해보면 되고, 미리 알고있다면? 알고 있는 값부터 시작하면 됩니다. 이렇게 되면 최대 증가 길이를 구하고, 증가 판정을 하는데 걸리는 시간이 O(N)이고, 길이가 N번인 수열에 대해 1번위치부터 N번위치까지 위의 작업을 수행하는데 O(N)의 시간복잡도가 소요되게 되니, 총 O(N^2)의 시간복잡도로 문제를 해결할 수 있습니다.

다음은 소스코드입니다.

혹시라도 해설이 틀린 부분이 있다면 언제든 말씀해 주세요 !!

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
typedef int I;
typedef vector<I> VI;
 
VI arr;
I N;
 
void inputData();
I max(I, I);
I lis(const VI&);
I lis2(I);
void init();
 
I cache[1000];
 
int main(){
        init();
        inputData();
        I begin, maxLen = 0;
 
        for (begin = 0; begin < N; begin++){
            maxLen = max(maxLen, lis2(begin));
        }
 
        cout << maxLen << endl;
        arr.clear();
    
 
 
    return 0;
}
 
I max(I a, I b){
    return (a > b ? a : b);
}
 
I lis2(I start){
    I& ret = cache[start];
    if (ret != -1){ return ret; }
 
    ret = 1;
    I next;
    for (next = start + 1; next < arr.size(); next++){
        if (arr[start] < arr[next]){
            ret = max(ret,lis2(next) + 1);
        }
    }
    return ret;
 
}
 
void inputData(){
    I cnt, num;
    cin >> N;
    for (cnt = 0; cnt < N; cnt++){
        cin >> num;
        arr.push_back(num);
    }
}
 
void init(){
    I idx;
    for (idx = 0; idx < 1000; idx++){
        cache[idx] = -1;
    }
}