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가 더 작을 경우 이분탐색을 통해 해당 원소가 들어갈 수 있는 자리를 탐..

Concept 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 아래와 같은 수열이 있을 때 오름차순으로 정렬된 부분 수열은 1,3,5 1,3,4 3,5 1,2,4 등과 같이 존재하며, 해당 수열에서 최장 증가 부분 수열은 3 Feature 이러한 LIS의 길이를 구하는 방법 중 단순한 접근법은 Brute-Force방법으로 수열의 총 길이가 K라고 가정할 때 1개 이상의 원소를 가지는 모든 부분수열의 경우의 수는 2^K개로 모든 부분 수열의 오름차순 정렬을 확인하는 것은 시간이 매우 오래 걸린다. LIS의 길이를 구하는 최적 방법에는 2가지가 있다. 다이나믹 프로그..