LIS

문제링크: Longest Increasing Sequence

증가하는 부분 수열의 갯수를 구하는 문제이다. 

동적계획법으로 풀 수 있으며, 아래보다 더 최적화된 O(NlogN) 방법이 가능하지만, 그 방법은 해당 수열을 저장하지 않는 방법이므로 일단 동적계획법을 이용해서 구현해 보았다. 

현재 숫자보다 큰 숫자를 만나면 1을 더해주고, 해당숫자를 재귀적으로 호출해서 해결한다. 

#include <iostream>
using namespace std;
#define max(a,b) ((a)>(b) ? (a):(b))
int C, N;
const int MAXNUM=100001;
const int MAXN = 501;
int Num[MAXN];
int Cache[MAXNUM];
int lis(int start) {
    int &ret = Cache[start];
    if (ret != -1) return ret;  
    ret = 1;
    for (int i = start + 1; i < N; i++) {
        if (Num[start] < Num[i])
            ret = max(ret, lis(i) + 1);
    }
    return ret;
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> Num[i];
            Cache[i] = -1;
        }
        int ret = 1;
        // 각 자리에서 시작하는 lis 길이 비교
        for (int i = 0; i < N; i++)
            ret = max(ret, lis(i) + 1);
        ret = ret - 1;
        cout << ret << endl;
    }
    return 0;
}

- 최적화하기

main에서 각 자리마다 lis를 호출해주어야 하는데 아래와 같이 최적화 가능하다. 

숫자 입력을 0~N-1에 받지말고, 1~N까지 받게 하고,

Num[0]에는 최소입력(1)보다 작은 0값을 넣는다. 

그리고 lis안에서 처리하도록 하면, main에서의 for를 없앨 수 있다. 

start가 0일 경우에는 if 내에 조건문을 비교하지 않고, 무조건 ret = max(ret, lis(i) + 1)을 호출하도록 조건을 변경했다. 

#include <iostream>
using namespace std;
#define max(a,b) ((a)>(b) ? (a):(b))
int C, N;
const int MAXNUM=100001;
const int MAXN = 501;
int Num[MAXN];
int Cache[MAXNUM];
int lis(int start) {
    int &ret = Cache[start];
    if (ret != -1) return ret;  
    ret = 1;
    for (int i = start + 1; i <= N; i++) {
        if (start == 0 || Num[start] < Num[i])
            ret = max(ret, lis(i) + 1);
    }
    return ret;
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N;
        Num[0] = 0;
        Cache[0] = -1;
        for (int i = 1; i <= N; i++) {
            cin >> Num[i];
            Cache[i] = -1;
        }
        int ret;
        // lis를 구한다. 
        ret = lis(0) - 1;
        cout << ret << endl;
    }
    return 0;
}

- 값 출력하기

값은 간단히 위 코드에서 max 값을 구할 때, 각 자리를 저장해두면 된다.

여기서 헷갈리는 게.. Order에 저장되어 있는 index에 있는 숫자를 차례대로 출력하면 엉뚱한 게 나온다. 

재귀적으로 호출하면서 값을 저장하게 됨을 기억해야한다!!!

Order에는 Order[2]=5, Order[5]=6 --> 2,5,6 자리의 각 자리값을 가리키게 저장해두었으므로, 

출력 시, 각 자리값을 쫓아가며 해당 자리에 있는 숫자를 출력하면 된다. 

#include <iostream>
using namespace std;
#define max(a,b) ((a)>(b) ? (a):(b))
int C, N;
const int MAXNUM=100001;
const int MAXN = 501;
int Num[MAXN];
int Cache[MAXNUM];
int Order[MAXN];
 
int lis(int start) {
    int &ret = Cache[start];
    if (ret != -1) return ret;  
    ret = 1;
    int next = 0;
    for (int i = start + 1; i <= N; i++) {
        if (start == 0 || Num[start] < Num[i]) {
            int cand = lis(i) + 1;
            if (ret < cand) {
                ret = cand;
                next = i;
            }
        }
    }
    Order[start] = next;
    return ret;
}
void printOrder(int len) {
    int next = 0;
    for (int i = 0; i < len;i++) {
        next = Order[next];
        cout << Num[next] << " ";
    }
    cout << endl;
}
 
void printOrder2(int start, int k, int len) {
    if (k == len) {
        cout << endl;
        return;
    }
    int next = Order[start];
    cout << Num[next] << " ";
    printOrder2(next, k+1, len);
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        // init 
        Num[0] = 0;
        Cache[0] = -1;
 
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> Num[i];
            Cache[i] = Order[i] = -1;
        }
        int ret;
        ret = lis(0) - 1;
        cout << ret << endl;
        printOrder(ret);
        printOrder2(0, 0, ret);
    }
    return 0;
}