최장 증가 부분 수열 ( LIS )

Table of Contents

개요

O(n^2) 풀이

더 알아보기 : O(n log n) 풀이 1

더 알아보기 : O(n log n) 풀이 2

1. 개요

 최장 증가 부분 수열 (longest increasing subsequence) 문제는 유명한 동적 계획법 활용 예시입니다. LIS 문제는 말 그대로 수열이 주어졌을 때, 수가 점점 증가하는 가장 긴 부분 수열을 찾는 문제입니다. 정확한 문제는 아래의 링크를 통해 확인할 수 있습니다.

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

2. O(n^2) 풀이

 dp [ i ] = A [ i ] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이

 간단하게 위와 같이 dp 문제를 정의하면 해결할 수 있습니다. 이 dp의 정의는 A[1] ~ A[i] 수열의 LIS 아니라, A[i]를 마지막 원소로 하는 LIS이기 때문에 A[i]는 꼭 포함된다는 걸 유의하시길 바랍니다.

 일단 경우의 수를 A [ i ] 바로 앞의 숫자가 무엇인지에 따라 나누어 보겠습니다.

1. 앞의 숫자가 없을 경우 : 최장 길이는 1 입니다다. ( A[i] 혼자 있는 경우입니다. )

2. 앞의 숫자가 A [ 1 ] 인 경우 : 최장 길이는 dp [ 1 ] + 1 이 됩니다.

    ( dp[1]에 이미 A[1]을 마지막으로 하는 최장 길이가 저장되어 있기 때문에, 그 뒤에  A[i]가 붙은 결과인 dp[1]+1이 최선입니다.)

    ( 단, A [ 1 ] >= A [ i ] 인 경우엔 A [ i ] 가 뒤에 올 수 없으므로 0 입니다.)

3. 앞의 숫자가 A [ 2 ] 인 경우 : 최장 길이는 dp [ 2 ] + 1 이 된다.

    ( 단, A [ 2 ] >= A [ i ] 인 경우엔 A [ i ] 가 뒤에 올 수 없으므로 0 입니다.)

...

Last. 앞의 숫자가 A [ i-1 ] 인 경우 : 최장 길이는 dp [ i-1 ] + 1 이 된다.

  ( 단, A [ i-1 ] >= A [ i ] 인 경우엔 A [ i ] 가 뒤에 올 수 없으므로 0 입니다.)

 위와 같이 경우를 나누면 이전에 저장해 놓은 dp [ 1 ] ~ dp [ i-1 ] 을 통해 답을 구할 수 있습니다. 그리고 최종 정답 = dp [ 1 ] ~ dp [ n ] 중 최댓값이 됨은 자명합니다.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
 
using namespace::std;
 
int n, ans;
int a[1005];
int dp[1005];
 
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++)
            if(a[i]>a[j])
                dp[i] = max(dp[i], dp[j]+1);
        ans = max(ans, dp[i]);
    }
    printf("%d",ans);
    return 0;
}
 

 동적 계획법을 처음 배울 때는, 보통 위에서 설명한 O(n^2) 방법으로 배우지만, 사실 더 효율적인 방법도 존재합니다. 그 중 유명한 2가지를 '더 알아보기'에서 소개하도록 하겠습니다.

 아래의 '더 알아보기'는 동적 계획법을 처음 배울 때는 이해가 어려울 수 있으므로, 해당하는 자료구조나 알고리즘을 아는 상태에서 보시는 걸 추천합니다.

O(n log n) 풀이 1은 Segment tree 라는 자료구조를 활용한 것이고

O(n log n) 풀이 2는 이분 검색 ( binary search ) 를 활용한 것입니다.

3. 더 알아보기 : O(n log n) 풀이 1

 위의 O(n^2) 풀이는 자료구조 중에서 Segment tree 를 적용시키는 것 만으로도, 간단하게 시간 복잡도를 줄일 수 있습니다.

 만일 dp[0] ~ dp[i-1]값을 이미 구했으며 A [ j ] 위치(인덱스)에 dp [ j ] 값를 저장해 놓은 segment tree를 구성해 놓았다고 하면, 아래와 같이 간단하게 dp[i]를 얻을 수 있기 때문이지요.

 dp[i] = 0 ~ A[i]-1 의 구간의 최댓값 + 1

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
// MAX 버전 segment tree 부분 시작
 
typedef int node_type;
 
node_type INIT = 0;
node_type node_calc(node_type n1, node_type n2){return max(n1,n2);}
 
struct segment_tree{
    int tree_n;
    vector<node_type> tree;
 
    void init(vector<node_type>& v){
        tree.resize(4*v.size()+1);
        for(int i=0; i<tree.size(); i++)
        tree[i]=INIT;
 
        tree_n=1;
        while(tree_n<v.size()) tree_n<<=1;
        for(int i=0; i<v.size(); i++)
            tree[tree_n+i-1]=v[i];
 
        for(int i=tree_n-2; i>=0; i--)
            tree[i] = node_calc(tree[i*2+1], tree[i*2+2]);
    }
 
    void init(int vn){
        vector<node_type> v(vn+1,INIT);
        init(v);
    }
    
    void recalc(int position){
        while(position!=0){
            position = (position-1)>>1;
            tree[position] = node_calc(tree[position*2+1], tree[position*2+2]);
        }
    }
    // position에 기존 값과 v를 node_calc한 결과를 넣음
    void update_calc(int position, node_type v){
        position+=tree_n-1;
        tree[position] = node_calc(tree[position], v);
        recalc(position);
    }
 
    node_type query(int a, int b, int idx, int left, int right){
        if(right<=a || left>=b) return INIT;
        if(left>=a && right<=b) return tree[idx];
        int mid=(left+right)/2;
        return node_calc(query(a,b,idx*2+1,left,mid),query(a,b,idx*2+2,mid,right));
    }
    node_type query(int a, int b){ // [a,b)
        return query(a,b,0,0,tree_n);
    }
}smtree;
 
// MAX 버전 segment tree 부분 끝
 
int n, ans;
int a[1005];
int dp[1005];
 
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    
    smtree.init(1005);
    for(int i=1; i<=n; i++){
        dp[i] = smtree.query(0,a[i])+1;
        smtree.update_calc(a[i],dp[i]);
        ans = max(ans, dp[i]);
    }
    printf("%d",ans);
    return 0;
}
 

4. 더 알아보기 : O(n log n) 풀이 2

 이번에는 이분 검색을 활용하는 방법입니다. 여기에서는 새로운 배열을 하나 추가하고, 갱신해 나가야 합니다.

 table [ i ] = 길이가 i 인 증가 부분 수열의 마지막 숫자 중 최솟값

 ('A[1] ~ A[k-1] 수열에 대한 table' -> 'A[1] ~ A[k] 수열에 대한 table'로 갱신시켜 나가야 합니다.)

 지금까지 찾은 길이가 i 인 부분 수열 중에서, 마지막 숫자가 가장 작은 것만 중요하고 나머지 부분 수열은 필요가 없다는, 탐욕법( greedy )스러운 접근 방식입니다. (마지막 숫자가 큰 것이 최종 LIS에 쓰인다고 해도 마지막 숫자가 작은 것으로 바꿔치기 할 수 있음은 쉽게 증명할 수 있습니다.)

 어찌됐든, 위와 같은 배열을 완성시킨다면, 정답 = table [ i ] 값이 존재하는 가장 큰 i 가 됨은 자명합니다.

 이제 A[1] ~ A[k-1] 수열에 대한 table을 가지고 있다고 했을 때, 이 걸 A[1] ~ A[k] 수열에 대한 table 로 갱신시키는 방법을 찾아야 합니다. 최종적으로 A[1] ~ A[n] 수열에 대한 table을 가지게 되면 정답을 찾을 수 있지요.

 그런데 생각해 보면 table[i] < A[k] 일 경우 table[i]은 갱신이 불가능하며,

( * table[i] 는 최솟값만 저장하기 때문에, table[i] = A[k] 를 할 일이 없기 때문입니다.)

 동시에 table[i-1] < A[k] 이어야 table[i] 를 A[k] 로 갱신할 수 있습니다.

( * 그래야 table[i-1] 로 끝나는 부분 수열의 뒤에 A[k]를 붙일 수 있기 때문입니다.)

 결국 table[i] 가 A[k]로 갱신되려면 이  조건을 만족 시켜야 합니다 . table[i-1] < A[k] && A[k] <= table[i]

 이 조건을 모두 만족하는 table 의 인덱스는

lower_bound(table.begin(),table.end(),a[k])

 뿐임은 lower_bound의 정의를 통해 쉽게 알 수 있습니다. 이제 이를 활용해 아래와 같이 코딩하면 완성입니다.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace::std;
 
int n;
int a[1005];
int dp[1005];
vector<int> table;
 
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    table.push_back(0);
    for(int i=1; i<=n; i++){
        int idx = lower_bound(table.begin(),table.end(),a[i])-table.begin();
        if(idx==table.size()) table.push_back(a[i]);
        else table[idx] = a[i];
    }
    printf("%d",table.size()-1);
    return 0;
}