LIS

LIS

최대 증가 부분수열(Longest Inceasing Sub-sequence) 문제.

증가하는 부분 수열은 완전 탐색으로 풀 수 있지만, 수열의 길이가 증가할수록 엄청나게 연산 시간이 증가하게 된다.

최대 증가 수열 같은 경우에는 배열에서 계속 오른쪽으로 이동하면서 부분 문제가 줄어든다.

그리고 왼쪽의 배열 값들은 고려할 필요가 없기 때문에, 최적 부분 구조를 이루므로 동적 계획법을 이용한 풀이가 가능하다.

cache[X] = X 에서 시작하는 부분 수열의 최대 길이

라는 점화식을 이용하면 결국 각 인덱스에서 구할 수 있는 부분 수열의 최대 길이가 구해지게 된다.

for문을 이용해서 X 다음 인덱스인 X+1 부터 돌면서 , Cache[X] 보다 값이 큰 인덱스를 찾아가면서 재귀함수를 수행한다.

그러면 결국 마지막에는 cache 안의 모든 값들 중에서 최대 값을 구해서 출력을 해주면 된다.

<정답 코드>

#include<iostream>
#include<vector>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
 
int cache[501];
int n, ans;
void init()
{
    ans = 0;
    for (int i = 0; i < 501; i++)
        cache[i] = 0;
}
int getLIS(const vector<int> &list,int k)
{
    
    //cache 값이 이미 존재할 때 cache 값 리턴
    if (cache[k + 1] != 0)
        return cache[k + 1];
 
    //모든 숫자는 길이가 최솟값이 1을 가짐.
    cache[k + 1] = 1;
 
    //k번째 다음 위치에서 , k번째 값보다 큰 값을 찾아서 재귀함수
    //k==-1 은 맨처음 시작하는 인덱스이므로 예외처리
    for (int i = k+1; i < list.size(); i++) {
        if (k == -1 || list[k] < list[i])
            cache[k + 1] = MAX(cache[k + 1], getLIS(list, i)+1);
    }
 
    return cache[k + 1];
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cin >> n;
 
        //변수들 초기화 함수 실행
        init();
        vector<int> list(n);
 
        for (int i = 0; i < n; i++) {
            cin >> list[i];
        }
        
        getLIS(list,-1);
 
        //구한 cache 값에서 최대값을 찾기
        for (int i = 1; i <= 500; i++)
            ans = MAX(ans, cache[i]);
 
        cout << ans << endl;
 
    }
 
    return 0;
}