devbelly

문제 www.acmicpc.net/problem/12014 알고리즘 LIS, 이분 탐색 풀이 $N$일 동안의 주가가 주어졌을 때, $K$일 동안 첫날을 제외하고 직전 날 산 주가보다 비싸게 구매할 수 있는지를 묻고 있습니다. 유명한 Longest Increasing Subsequence 문제입니다. 다이나믹 프로그래밍으로 $O(N^2)$에 해결 가능합니다. 하지만 주어지는 테스트케이스가 100개에 $N$제한이 1만이므로 해당 알고리즘을 사용하면 시간 초과가 발생합니다. 처음에 정렬된 배열을 하나 갖고 시작합니다. 처음이므로 정렬된 빈 배열을 갖고 있습니다. $N$개의 값을 순차적으로 보며 해당 값을 정렬된 배열 어디에 위치한지 찾습니다. 정렬된 배열에서 위치를 찾는 것이므로 이분 탐색으로 찾을 수 있습니..