boj 12015 c++ 정답

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. Logic 이전 가장 긴 증가하는 부분 수열 문제에서는 DP를 사용해서 풀었다. DP를 사용하는 풀이에서는 전체를 돌면서 확인 하며 메모이제이션 했기때문에 시간복잡도가 O(N^2)이었다. 하지만 이 문제에서는 입력값이 엄청 많기 때문에 N^2으로 풀지 못하기 때문에 시간복잡도가 O(nlogn)을 가지는 이분탐색 기반으로 풀어야 한다. binary search를 구현해서 푸는 방법과 C++의 ..