LIS 문제를 세그먼트 트리를 이용하여 풀이하는 방법

제목에서 알 수 있듯이, LIS 문제를 O(N log N)의 시간복잡도로 세그먼트 트리를 이용하여 풀 수 있다.

 

 

예제로

 

9
9 5 4 6 1 3 7 10 2

 

라는 입력이 주어진다고 해보자. 여기서 LIS는 무엇일까?

LIS = { 5, 6, 7, 10 }, 혹은 { 4, 6, 7, 10 }, 혹은 { 1, 3, 7, 10 } 등으로, 길이는 4이다.

우리는 만약에 N >= 10,000 이상의 입력이 들어온다면, O(N^2)의 dp 알고리즘으로는 풀 수 없으므로,

O(N log N) 의 풀이를 알아야 한다.

 

그리고 우리는 세그먼트 트리를 활용한 구간 최댓값을 구하는 것으로 이를 풀 수 있다.

 

예제를 예로 들겠다. 배열 요소가 저장된 배열을 S라 할 때, S는 다음과 같이 표현된다.

 

S

9

5

4

6

1

3

7

10

2

 

에 대해, 오름차순 정렬을 한다. 그 배열을 R이라 하겠다.

 

R

1

2

3

4

5

6

7

9

10

 

그리고, D[i] = 1~i번 인덱스까지의 수열의 LIS 를 뜻하는 배열 D를 정의한다.

초기값은 모두 0이다.

 

D

0

0

0

0

0

0

0

0

0

 

이 세 개의 배열에 대해, N번 반복한다:

 

S	9	5	4	6	1	3	7	10	2
R	1	2	3	4	5	6	7	9	10
D	0	...
INDEX	0	1	2	3	4	5	6	7	8

 

i = 0일 때, R[i] = 1이고, R[i]를 배열 요소로 가지는 S 배열의 인덱스는 4이다.

S[4] = R[0] = 1 이기 때문이다. 이 인덱스를 r이라 하겠다. i = 0일때, r = 4이다.

이때 우리는 D[0~r-1] 의 최댓값 + 1이 D[r]의 값이 되는 것을 알 수 있고, 구간의 최댓값을 구하는 것이기 때문에 세그먼트 트리를 이용하여 O(log N)만에 구할 수 있다.

이때 D[0~3]의 최댓값 ( = M(D[0~3] ) 은 0이므로 D[4] = 1이다.

 

D	0	0	0	0	1	0	0	0	0
INDEX	0	1	2	3	4	5	6	7	8

 

i = 1일 때, R[i] = 2이기 때문에 r = 8이다. M(D[0~7]) = 1 (D[4]가 1으로 최댓값) 이므로 D[8] = 2이다.

 

D	0	0	0	0	1	0	0	0	2
INDEX	0	1	2	3	4	5	6	7	8

 

i = 2일 때, R[i] = 3이기 때문에 r = 5이다. M(D[0~4]) = 1 (D[4]가 1으로 최댓값) 이므로 D[5] = 2 이다.

 

D	0	0	0	0	1	2	0	0	2
INDEX	0	1	2	3	4	5	6	7	8

 

i = 3 일 때, r = 2 이다. 따라서 D[2] = 1이다.

 

D	0	0	1	0	1	2	0	0	2
INDEX	0	1	2	3	4	5	6	7	8

 

이러한 로직으로 D 배열을 채워나가보자. 마지막 단계에는 다음과 같은 테이블이 만들어진다.

이렇게 해서 D 배열은 O(N log N)만에 채워졌다.

 

D

1

1

1

2

1

2

3

4

2

 

여기서 LIS의 길이는 4라는 것을 알 수 있다. 하지만 LIS의 길이를 출력하는 것이 아닌, LIS를 출력하는 문제라면 어떻게 할까? 이는 어려울 것이라 생각되지만, 사실은 쉽다. 여기서 D 배열이 의미하는 것이 뭘까? 우리는 아까 D[i]를 정의했다: 1~i번 인덱스까지의 수열의 LIS

이는 약간 겹치는 부분이 있지 않는가? 이 문제를 DP로 풀이할 때 DP배열의 의미와 똑같다. 실제로 dp 배열을 채워보면 D 배열과 정확히 일치하는 것을 알 수 있다.

이제 문제는 한결 쉬워진다. 아니, 너무 쉬워진다. 우리는 아마 이 LIS 문제에서 LIS를 알아내보았을 것이다. 같은 로직으로 풀이하면 된다.

 

ptr = LIS의 길이 라 할 때, i = N-1 부터 i를 감소시켜나가며, ptr를 찾는 때마다 ptr를 1 감소 시키고, 스택에 S[i]를 넣는다. ptr가 0이라면 반복을 중지한다.

 

의 로직으로 풀 수 있다. 그렇다면 이 예제에서 출력은

 

4
1 3 7 10

 

이 나오고, 이는 예제의 답이라는 것을 알 수 있다.

 

이로써 LIS 문제를 세그먼트 트리로 푸는 방법을 알아보았다. 이런 문제가 과연 있을까?

놀랍게도 이 LIS 문제 에서 활용할 수 있다. 이 문제에서 유의할 점은 정렬이다. 자세한 설명은 코드를 참조.

 

난이도(객관적): Platinum V

난이도(개인적): Platinum V

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;
#define MAXN 1000001

int N;
vector<int> S;
vector<int> D = vector<int>(MAXN);
vector<pair<int, int> > R;
vector<int> tree = vector<int>(MAXN * 4);

bool cmp(pair<int, int> left, pair<int, int> right) {
    if (left.first == right.first) return left.second > right.second;
    else return left.first < right.first;
}

int query(int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 0;
    }
    if (left <= start && end <= right) {
       return tree[node];
    }
    int mid = (start + end) / 2;
    int lmax = query(node * 2, start, mid, left, right);
    int rmax = query(node * 2 + 1, mid + 1, end, left, right);
    return max(lmax, rmax);
}

void update(int node, int start, int end, int idx, int val) {
    if (idx < start || idx > end) return;

    if (start != end) {
        int mid = (start + end) / 2;
        update(node * 2, start, mid, idx, val);
        update(node * 2 + 1, mid + 1, end, idx, val);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }
    else {
        tree[node] = val;
    }
}

void update(int val, int idx) {
    D[idx] = val;
    update(1, 0, N - 1, idx, val);
}

int main() {

    cin >> N;
    for (int i = 0; i < N; i++) {
        int inp; cin >> inp;
        S.push_back(inp); R.push_back( { inp, i } );
    }

    sort(R.begin(), R.end(), cmp);

    for (int i = 0; i < N; i++) {
        int v = R[i].first;
        int r = R[i].second;
        int maxi = query(1, 0, N - 1, 0, r - 1);

        update(maxi + 1, r);
    }

    int mx = 0;
    for (int i = 0; i < N; i++) {
        mx = max(D[i], mx);
    }

    cout << mx << endl;

    stack<int> ans;
    for (int i = N - 1; i >= 0; i--) {
        if (mx <= 0) break;
        if (D[i] == mx) { mx--; ans.push(S[i]); }
    }

    while (!ans.empty()) {
        cout << ans.top() << " "; ans.pop();
    }

    cout << endl;
}