LIS (Longest Increasing Subsequence)

우선, $O(N^2)$ DP 풀이부터 살펴 보자.

$dp[i]$ = $0$ ~ $i$ 구간에서 $i$를 끝으로 하는 lis의 최대 길이

$dp[i]$ = $0$ ~ $i-1$ 의 $j$ 에 대하여 $arr[i]>arr[j]$를 만족하고, $dp[j]+1$의 최대값을 만족한다.

여기서는 구현할 때 처음에 NEGINF, 끝에 INF 를 추가해서 구현하였고, 동시에 전 단계로의 선택 과정을 담아 복원까지 했다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;
const int INF = numeric_limits<int>::max();
const int NEGINF = numeric_limits<int>::min();

int n, arr[MAXN+10], dp[MAXN+10], choice[MAXN+10];

vector<int> ans;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &arr[i]);
    arr[0]=NEGINF;
    arr[n+1]=INF;

    for(i=1; i<=n+1; i++)
    {
        dp[i]=1;
        choice[i]=0;
        for(j=0; j<i; j++) if(arr[j]<arr[i]) if(dp[i]<dp[j]+1)
        {
            choice[i]=j;
            dp[i]=dp[j]+1;
        }
    }

    i=choice[n+1];
    while(i!=0)
    {
        ans.push_back(arr[i]);
        i=choice[i];
    }
    reverse(ans.begin(), ans.end());

    printf("%d\n", dp[n+1]-1);
    for(i=0; i<ans.size(); i++) printf("%d ", ans[i]);
}

 

시간 복잡도 : $O(N^2)$

 

하지만 LIS 는 $O(NlgN)$ 에 구할 수 있다.

세그먼트 트리를 사용하거나, 이진탐색을 사용하는 것이다.

이진탐색 $O(NlgN)$ 풀이는 다음과 같다.

V라는 벡터를 유지하며, V[i] = i의 길이를 갖는 LIS 의 끝의 최솟값을 의미한다.

따라서 지금 추가하려는 원소가 V의 모든 원소보다 크다면 뒤에 추가해주고,

아니라면 lower_bound 를 찾아 그 부분을 바꿔주면 된다.

 

 현재 배열에 8 12 15가 있다고 가정하자.

9를 추가할 차례라면, 9는 lower_bound 의 위치인 12를 덮어씨우고 들어가게 된다.

그럼 왜 이것이 성립할까?

1번재 칸이 8이란 것은 길이 1인 LIS 중에 끝이 8이 최소라는 것이다.

그렇다면 그 다음에 12 대신 9를 추가할 수만 있다면 길이 2이고, 마지막 값이 12보다 작은 9인 길이 2의 LIS 가 된다.

 

여기서도 복원을 해야 하는데, 비교적 간단하다.

DP에서 choice 배열에 담겨 있는 것은 그 번째에서 전 단계로 선택한 최적의 단계를 의미한다.

여기서도 $a1, a2, ..., aj, X, ... $위치에서 $X$에 덮어 씨웠다면 그 이유는 $aj$의 LIS 에 $X$를 붙인게 더 이득이기 때문이다.

따라서 $X$가 가르키는 LIS 의 전항은 무조건 $aj$이다.

이와 같이 그 전 선택만을 저장해 준다면 이것으로 똑같이 복원해 줄 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const int NEGINF = numeric_limits<int>::min();
const int INF = numeric_limits<int>::max();

int n, arr[MAXN+10];
int choice[MAXN+10];

vector<int> ans;

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &arr[i]);
    arr[n+1]=INF;

    vector<int> V, P;
    V.push_back(NEGINF); P.push_back(0);

    for(i=1; i<=n+1; i++)
    {
        if(V.back()<arr[i])
        {
            choice[i]=P.back();
            V.push_back(arr[i]);
            P.push_back(i);
        }
        else
        {
            int t=lower_bound(V.begin(), V.end(), arr[i])-V.begin();
            V[t]=arr[i];
            P[t]=i;
            choice[i]=P[t-1];
        }
    }

    i=choice[n+1];
    while(i!=0)
    {
        ans.push_back(arr[i]);
        i=choice[i];
    }

    reverse(ans.begin(), ans.end());

    printf("%d\n", V.size()-2);
    for(i=0; i<ans.size(); i++) printf("%d ", ans[i]);
    return 0;
}

시간 복잡도 : $O(NlgN)$

 

* 문제 : https://www.acmicpc.net/problem/14003

* 참고 : http://codedoc.tistory.com/414