기록방

👉 문제링크 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 🔸 문제 분석 🔸 주어진 수열 A의 가장 긴 증가하는 부분 수열 (LIS)의 길이를 출력한다. 🔸 문제 풀이 🔸 n이 100만이므로 LIS의 간단한 풀이 법인 DP를 사용하면, O(n^2)으로 1조로 시간을 초과한다. LIS의 두 번째 풀이법인 이분 탐색을 이용해 O(nlogn)으로 풀이한다. (600만) LIS 배열을 입력 배열 원소를 하나씩 골라 채워간다. 입력 배열의 원소를 채울 자리는 이분 탐색으로 구한다. 🔸 코드 🔸 import java.i..