알고리즘
[알고리즘] 최장 증가 부분 수열(LIS) 알고리즘
🧐 최장 증가 부분 수열 (LIS)란? 최장 증가 부분 수열, Longest Increasing Subseqeunce는 어떠한 수열의 부분 수열중 오름차순으로 증가하는 가장 긴 수열을 의미한다. (이때 각 원소는 연속할 필요는 없다.) 아래의 예시 수열을 보자. [ 7, 3, 5, 2, 7, 4, 8, 2] 이 수열에서 증가하는 순열에는 [2, 4], [2, 4, 8], [3, 5] 등 다양한 것이 있지만 LIS는 [3, 5, 7, 8]이 된다. 📝 LIS를 구해보자 LIS를 구하는 방법에는 동적 계획법(DP)와 이분탐색으로 크게 두가지의 방법이 있다. DP는 $O(n^2)$의 시간복잡도를 보이며, 이분탐색으로 구현하게 되면 $O(n\log{n})$의 시간복잡도가 나타난다. 1) 동적 계획법 (Dynam..
