LIS - Longest Increasing Subsequence최장 증가 부분수열을 구하는 알고리즘백준 - 12015 가장 긴 증가하는 부분 수열 2해당 문제는 단순하게 완전탐색으로 풀면 단순하게 풀리는 문제이다. 하지만 문제점은 역시나 시간 복잡도...완전 탐색으로 풀게되면 시간 복잡도는 O(n^2)으로 매우매우매우 느린 편이다.이 방식의 문제를 더 효율적으로 푸는 방법이 두 가지 있는데 하나는 dp를 이용한 방식이고 하나는 이분 탐색을 이용한 방식이다. 나는 여기서 이분 탐색을 이용한 방식을 다뤄보려 한다.이분 탐색을 이용한 방식의 시간 복잡도는 O(nlogn)이다. 이제 어떤 방식으로 최대 증가 부분수열을 찾는지를 알아보자.(정확히는 이 방식은 부분수열의 크기만을 찾아내는 알고리즘이다. )개괄적인..