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 수열의 크기가 백만 단위라서 N^2 의 DP로는 문제로 풀 수 없다. Binary Search를 활용해서 O(NlogN)으로 풀어낼 수 있다. 자세한 풀이는 최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기 LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다. 개인적..
