어흥

문제 링크: 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. 주의할 점 - 직전의 게시물과 같이 N^2의 시간복잡도를 지니는 방법으로는 TLE가 난다 - 이분탐색을 사용하여 NlgN의 시간복잡도를 지니게 한다 2. 구현 - 모든 배열에 대한 정보를 Arr[] 배열에 저장하고 Dp[0]= Arr[0], idx=0으로 초기화한다 - i: 1~Num-1까지 For문을 수행하며, Dp[idx]< Arr[i]인 경우, 무조건 추가한다 - 이외의 경..