Algorithms
-
Longest Increasing Subsequence (LIS)를 NlogN에 구하기
최장 증가 수열이라고 불리는 Longest Increasing Subsequence (LIS)라는 문제는 간단하지만 강력한 문제 중 하나이다. 이 문제는 다이나믹 프로그래밍을 활용한 $O(N^2)$ 풀이와 이분 탐색을 활용한 $O(NlogN)$ 풀이가 잘 알려져 있는데, 이분 탐색을 활용한 풀이가 어떻게 최적화되었는지에 대한 설명을 이 글에서 적고자 한다. Naive solution: Bruteforcing 간단하게 생각해보자. 모든 부분 수열에서 오름차순을 이루는지 확인해보면 된다. 모든 원소가 부분 수열에 속하거나 속하지 않는 두 가지 상태를 가진다. 길이 $N$의 수열이라면 $2^N-1$개의 부분 수열이⋯