[백준 12015번] 가장 긴 증가하는 부분 수열2 - 세그먼트 트리

---

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

---

 

목차

• 사전 지식
• DP 풀이
• 세그먼트 트리 풀이

 

가장 긴 증가하는 부분 수열 문제는 LIS(Longest Increasing Subsequences)로 잘 알려진 문제이다.

이번 글에서는 LIS 문제를 세그먼트 트리를 이용하여 풀어보겠다.

 

 

사전 지식

• LIS의 DP(Dynamic Programming) 풀이를 이해해야 한다. (링크)
• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)

 

 

 

DP 풀이 - $\scriptsize{O(N^2)}$

LIS를 푸는 가장 잘 알려진 방법은 DP를 이용하는 것이다.

배열의 각 원소를 탐색하며, 현재 원소를 끝으로 하는 가장 긴 LIS를 구하는 방법이다.

arr[i]: 인덱스가 i인 원소
dp[i]: 인덱스가 i인 원소로 끝나는 LIS 길이

dp[i]를 구하는 법은 인덱스 1부터 i-1까지 살펴보며 아래와 같은 코드로 구할 수 있다. (인덱스는 1부터 사용한다)

for (int i=1; i<=N; i++) {
   int best = 0;
   for (int j=1; j<i; j++) {
      if (arr[j] < arr[i]) best = max(best, dp[j]);
   }
   dp[i] = best + 1;
}

 

 

 

세그먼트 트리 풀이 - $\scriptsize{O(N \cdot \log N)}$

이 풀이는 DP 풀이의 논리는 비슷하지만, dp[i]를 갱신하는 과정이 $\log N$ 시간에 수행 가능하다.

 

세그먼트 트리의 리프 노드 인덱스는 배열의 인덱스가 아닌 원소들의 값에 대응되고,

리프 노드에 들어 있는 값은 (dp 풀이와 비슷하게) 그 값을 끝으로 하는 LIS 길이가 들어있다.

 

이렇게 구성하면 어떤 원소보다 작은 원소들 중에서 최대값을 세그먼트 트리를 이용하여 바로 구할 수 있다!

 

	// BOJ 12015
	// DP SegTree
	#include <bits/stdc++.h>
	using namespace std;
	int sz;
	vector<int> tree;
	void update(int idx, int x) {
	idx += sz;
	tree[idx] = x;
	while (idx /= 2) tree[idx] = max(tree[2*idx], tree[2*idx+1]);
	}
	int query(int a, int b) {
	a += sz; b += sz;
	int ret = 0;
	while (a <= b) {
	if (a%2 == 1) ret = max(ret, tree[a++]);
	if (b%2 == 0) ret = max(ret, tree[b--]);
	a /= 2; b /= 2;
	}
	return ret;
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	sz = (1 << ((int)ceil(log2((int)(1e6+1)))));
	tree.assign(2*sz, 0);
	int n; cin >> n;
	int res = 0;
	for (int _=0; _<n; _++) {
	int x; cin >> x;
	int best = query(0, x-1);
	update(x, best+1);
	res = max(res, best+1);
	}
	cout << res <<'\n';
	return 0;
	}

view raw 12015.cpp hosted with ❤ by GitHub