[최장 증가 부분 수열(LIS)] 최장 증가 부분 수열(Longest increasing subsequence) 알고리즘은 주어진 수열에서 제일 길게(=최장) 증가하는 부분적인 수열을 의미합니다. 문제를 해결할 수 있는 방법은 다양하지만, 보통 DP(동적 프로그래밍)와 Binary Search(이분 탐색)를 사용합니다. DP는 이중 for문을 사용하므로 시간복잡도가 O(n^2)이고 Binary Search는 O(nlogn) 시간복잡도를 가집니다. 그렇기 때문에 DP로 구현하지 않고 Binary Search로 구현하는 감각을 익혀야 합니다! 최장 증가 부분 수열 알고리즘으로 문제를 풀 수 있다는 가정 하에, Binary Search로 구현하면 n의 범위에 상관없이 해결할 수 있기 때문입니다. [DP를 활용..
