LIS(Longest Increasing Subsequence) - 가장 긴 증가하는 부분 수열

LIS(Longest Increasing Subsequence)는 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.

즉, 주어진 수열에서 일부 숫자를 제거하여 만든 부분 수열 중에서, 오름차순으로 정렬된 가장 긴 수열을 찾는 문제.
예를 들어, 수열 [10, 20, 10, 30, 20, 40]이 있다면, LIS는 [10, 20, 30, 40]이 된다.

예시 백준 문제는 여기 있다.

DP를 연습할때 가장 먼저 나오는 문제이지만, 의외로 2가지 실수하기 쉬운 포인트와. 한가지 인사이트를 제공한다.

 

2가지 실수하기 쉬운 포인트

아래는 이문제에 대한 정답코드인데, 아래 주석으로 여기라고 되어 있는 부분을 풀때마다 실수했다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// dp[3] = 5 ; 인덱스 3까지 가장 긴 증가하는 부분수열의 길이는 5이다.
int dp[1001]; 
int A[1001];

int main(void)
{
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", A + i),dp[i]=1;  // 여기. dp[i]=1초기화 부분!
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j]) 
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	int ans = 1;
	for (int i = 0; i < N; i++) ans = max(ans, dp[i]);  // 여기. dp[n-1]아니어도 답이 될 수 있음!
	printf("%d\n", ans);
	return 0;
}

 

한가지 인사이트

이 문제는 놀랍게도 recursive+memoization보다 iterative 방식이 더 생각하기 편하고,

편한 recursive+memoization을 떠올리면 dp[ix][cur_val] 형태가 돼서 냅색DP형태가 나오는데 문제 범위에 따라 메모리초과 오류가 발생하여 해결이 어렵다.

아래는 편한 recursive버전이다.

#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int in[1001];
int n;
int dfs(int ix, int cur_max_val){
    if(ix>=n) return 0;
    if(dp[ix][cur_max_val]) return dp[ix][cur_max_val];
    
    //포함
    int r1 = -1;
    if(cur_max_val < in[ix])
        r1= 1 + dfs(ix+1, in[ix]);
    
    //불포함
    int r2 = dfs(ix+1, cur_max_val);

    return dp[ix][cur_max_val] = max(r1,r2);
}
int main() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", in+i);
    printf("%d\n", dfs(0, 0));

    return 0;
}

자세히 들여다 보면, dp[n]을 1로 초기화 하는 부분도 필요없고, 마지막에 정렬하는 부분도 필요없어서 실수 확률이 확연히 줄어든다.

하지만 위 코드를 dp[ix]로 1차원만 사용하도록 변경하는건 쉽지 않다.

아래처럼 할 수 있긴한데, dfs함수내에 iterative한 부분이 들어 있어 완전한 DFS라고 부를 수 있을지 약간 애매하다.

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i) 
#define REP(i,n) FOR(i,0,n) 
typedef vector<int> VI;

int dp[1001];
int in[1001];
int N;
int go(int n)
{
         if(n==0) return 1;
         if(dp[n]) return dp[n];
 
         int maxR=1;
         REP(i,n){
            if(in[n] >in[i])
                maxR = max(maxR, go(i)+1);                 
         }
         return dp[n] = maxR;
}
 
int main()
{
        scanf("%d\n", &N);
        REP(i, N)scanf("%d",&in[i]); 
        int r=0;
        REP(i,N) r=max(r,go(i));
        cout << r <<endl;
        return 0;
}

 

실제 시퀀스를 출력하는 방법

아래처럼 prev배열하나를 추가하면 어렵지 않게 구현가능하다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// dp[3] = 5 ; 인덱스 3까지 가장 긴 증가하는 부분수열의 길이는 5이다.
int dp[1001];
int A[1001];
int prv[1001];

int main(void)
{
    fill(prv, prv + 1001, -1);
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)scanf("%d", A + i), dp[i] = 1; // 여기. dp[i]=1초기화 부분!
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (A[i] > A[j])
                if (dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    prv[i] = j;
                }
        }
    }
    int ans = 1;
    int end_ix = 0;
    for (int i = 0; i < N; i++)
    {
        if (ans < dp[i])
        {
            ans = dp[i];
            end_ix = i;
        }
    }
    printf("%d\n", ans);
    vector<int> v;
    v.push_back(A[end_ix]);
    while (prv[end_ix] != -1)
    {
        end_ix = prv[end_ix];
        v.push_back(A[end_ix]);
    }
    reverse(v.begin(), v.end());
    for (auto e : v)
        printf("%d ", e);

    return 0;
}