Concept 기존 dp 메모이제이션을 활용한 LIS에서 시간복잡도를 줄이기 위해 이분탐색을 활용 기존 LIS에서 앞쪽 수열을 보고 큰 값을 찾고 값을 갱신하는데 드는 시간인 O(N)을 줄일 수 없을까에서 비롯된 방식 사전지식으로 LowerBound 이분탐색에 대한 이해와 O(N^2)방식의 이해가 요구. Feature 시간복잡도의 경우 모든 원소를 탐색하는 시간 O(N)에 대해 이분탐색 O(NlogN)을 수행함으로 총 O(N * NlogN)이므로 O(NlogN)의 시간으로 최장 증가 수열을 구할 수 있음. Implement 1. 각각의 원소 i에 대해서 현재 기록된 lis배열의 끝 인덱스와 비교하여 i가 더 크다면 뒤에 추가 2. i가 더 작을 경우 이분탐색을 통해 해당 원소가 들어갈 수 있는 자리를 탐..