[백준 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 길이가 들어있다.

 

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