[BOJ] 2352 : 반도체 설계

출처 : https://www.acmicpc.net/problem/2352

이 문제는 최장증가부분수열(Longest Increasing Subsequence)을 구하는 문제이다.
최장증가부분수열은 간단하게 O(n^2)으로 쉽게 구할 수 있으나 이는 n의 크기가 증가하게 된다면 오랜 시간이 걸리게 된다.
다행히 LIS를 O(n log n)으로 구하는 방법이 있는데
첫번째는 segment tree를 이용하는 방법이나 이 방법은 LIS를 구하는데에는 상대적으로 많은 노력이 든다.
따라서 두번째 방법이 효율적이라 볼 수 있는데 그 방법은 이분탐색을 이용한 방법으로 다음과 같다.

계속해서 탐색을 하면서 최적의 위치에다가 수를 삽입하는 방법인데, 최적의 위치를 구할 때 이분탐색을 이용하게 된다.

이 문제는 겹치는 숫자가 없으므로 lower_bound 나 upper_bound 둘 다 이용해도 무관하다.


소스코드 : https://github.com/younghk/Problem_Solving/blob/master/BOJ/boj_2352.cpp





최장증가부분수열에 관한 내용을 잘 정리해 놓은 블로그가 있어서 링크를 달아놓는다.

Reference : https://jason9319.tistory.com/113