알고리즘 공부 : LIS

과학고에서 떨어진 나는 그동안 충격에 휩싸여 열심히 하지 않아 실력이 많이 줄었을거라 생각되니

 

더 열심히 재활 활동을 꾸준히 해보자.

 

소개할 알고리즘 : LIS 

 

LIS는 Longest Increasing Subsequence, 즉 최장 증가 부분 수열을 말한다.

 

*) 예를 들어 {10,20,10,30,20,50}이라는 배열이 있다고 가정하자. 

그렇다면 이 배열에서의 LIS는

{10, 20, 10, 30, 20, 50} => {10, 20, 30, 50}

이러한 상태가 된다.

 

이 LIS 알고리즘은 우리에게 특정한 배열에서의 LIS를 구해주는 알고리즘이다.

 

이 알고리즘에는 3가지 방법이 있다.

 

1. O(n^2) DP

2. O(n log n) Segment Tree 사실상 거의 안씀

3. O(n log n) Binary Search

 

이 순서대로 소개하겠다.

 

 

1. O(n^2) DP

 

다이나믹 프로그래밍(DP)를 이용한 아주 간단한 방법이다.

 

dp[i] = i번째 수를 마지막 원소로 가지는 LIS의 최대 길이

 

라고 정의하고 생각해보자.

 

그렇다면 만약 배열에서의 이전 값이 지금 값보다 작으면, 우리는 이전 값을 지금 값을 마지막 원소로 하는 LIS에 포함된다는 것을 알 수 있다.

 

간단히 말해서, 변수 i,j(1<=i<j<=n)가 있고 배열 a가 있다면, a[j]>a[i]일때 a[j]를 마지막 원소로 하는 LIS 배열에 a[i]가 포함된다는 뜻이다.

 

그렇다면 우리는 저 아이디어를 수용해서 dp식을 세운다면

 

dp[j] = max(dp[i]+1) (a[i]<a[j] && i<j)

 

이렇게 된다. 이때 저 max 값 때문에 O(n^2)의 시간복잡도를 가진다.

 

내가 아주 옛날에 짰던 O(n^2) 코드를 공개한다.

#include <bits/stdc++.h>
using namespace std;
int a[1001],dp[1001],n,maxx;
int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    dp[0] = 1;
    for(int i=0; i<n; i++){
        maxx = 0;
        for(int j=0; j<i; j++)
            if(a[i]>a[j])
                maxx = max(maxx,dp[j]);
        dp[i] = maxx+1;
    }
    cout << *max_element(dp,dp+n);
}

 

2. O(n log n) Segment Tree

 

다른 하나의 방법은 

 

세그먼트 트리를 이용하여 위 dp 식과 정의를 비슷하게 하여

 

매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 업데이트하는 방식으로 하면 된다.

 

사실 나도 소스를 안짜봐서 잘 모르겠다. 블로그를 참고한 내용이라...

 

3. O(n log n) Binary Search

 

이 방법이 제일 최고다. 물론 주관적으로 생각한거라 최고라고는 단정 지을 수 없다. 근데  ㄹㅇ 개꿀인 건 맞다. ㅋㅋ!

 

저 방법을 간단하게 말하자면,

 

LIS를 유지시키기 위한 최적의 자리에다가 수를 넣는 방법이다.

 

저 최적의 자리를 찾는 것은 LIS 배열(이 배열에 수열에서 나올 수 없는 최소의 숫자를 먼저 넣어놓고 시작한다.)을 만들어서

 

O(n)의 반복문을 돌리면서 LIS 배열의 마지막 원소를 현 배열 원소랑 비교한다.

 

만약 LIS 배열의 마지막 원소보다 비교하려는 값이 더 크면 그 비교하려는 값을 LIS에 추가해해주고, LIS 배열의 마지막 원소보다 비교하려는 값이 더 작다면 그 원소들 사이에서 자신이 그 원소와 바꿔치기 해도 LIS 배열이 유지되는 자리로 바꿔주면 된다.

 

이런 작업이 끝난 후 (LIS 배열의 크기-1(INF 때문에 하는 것))를 구하면 된다.

 

*) 예를 들어 A={1,3,2,5,4,6}이라는 배열이 있다고 가정하자.

그렇다면 알고리즘은 이렇게 수행된다.

INF = 수열에서 나올 수 없는 최소의 숫자.

LIS : {INF}, A={1,3,2,5,4,6}

LIS : {INF,1}, A={1,3,2,5,4,6}

LIS : {INF,1,3}, A={1,3,2,5,4,6}

LIS : {INF,1,2}, A={1,3,2,5,4,6}

LIS : {INF,1,2,5}, A={1,3,2,5,4,6}

LIS : {INF,1,2,4}, A={1,3,2,5,4,6}

LIS : {INF,1,2,4,6}, A={1,3,2,5,4,6}

 

LIS 길이 : 5-1 = 4

 

최적의 선택은 lower_bound로 O(log n)만에 구할 수 있다.

 

그러므로 총 O(n log n)의 시간복잡도를 가지게 된다.

 

소스 코드는 이렇다.

 

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e13+7;
ll n, a[MEM];
vector<ll> v;
main(){
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    v.push_back(-INF);
    for(int i=0; i<n; i++){
        ll q=a[i];
        if(v.back()<q)
            v.push_back(q);
        else{
            ll it = lower_bound(v.begin(), v.end(), q)-v.begin();
            v[it] = q;
        }
    }
    cout << n-v.size()+1 << '\n';
}

 

 

 

*연습 문제 *

 

1. 기본 1단계

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

아주 전형적이고 기본적인 LIS문제이다. 

 

2. 기본 2단계

www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

O(n log n)!

 

3. 응용

www.acmicpc.net/problem/18353

18353번: 병사 배치하기

www.acmicpc.net/problem/2352

2352번: 반도체 설계

www.acmicpc.net/problem/1818

1818번: 책정리

 

www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

4. 역추적 1단계

www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

O(n^2) 알고리즘의 역추적이다. 조금만 생각해보면 바로 나올 것이다.

 

5. 역추적 2단계

www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

O(n log n) 알고리즘의 역추적이다.

 

저 알고리즘에서 사람들이 많이 오해하는게 있는데 LIS 배열에는 제대로 된 LIS가 들어있지 않다.

 

왜 그런지 생각해보고, 어떤 방법을 쓸지 잘 생각해 보는 것을 추천한다. 글쓰기 전 본인은 방금 그랬음 ㅋㅋ

 

 

 

 

다음은 Sparse Table 공부할 거다. ㅋㅋ!