Computer Science/Algorithms

문제 개요 백준 12015번 문제입니다. LIS(Longest Increasing Sequence)의 길이를 $O(n\log n)$ 시간에 구해야 하는 문제로, 동적 계획법을 사용한 $O(n^2)$ 풀이와는 다른 방법이 필요합니다. 이진 탐색을 사용하여, LIS가 될 수 있는 후보군을 계속 갱신하는 방식의 풀이를 소개합니다. 문제 분석 새로운 원소 조회 동적 계획법 풀이와 같이 앞에서부터 원소를 하나씩 조회합니다. 지금까지 조회한 원소가 2와 5라고 합시다. LIS는 `2, 5` 일 것입니다. 이제 다음 원소가 3이라고 합시다. 가능한 LIS는 `2, 3` 과 `2, 5` 의 두 가지입니다. 그런데 마지막 원소가 작은 편이 뒤에 나올 원소들을 LIS에 넣기에 더욱 유리하므로, `2, 3` 을 선택하기로 ..