최장 증가 부분 수열(LIS) 알고리즘

LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다. 예를 들어, [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다. 증가하는 부분 수열 중 가장 긴 것이기 때문. LIS를 풀기 위한 가장 일반적인 방법은 DP를 이용하는 것이다. dp = [1]*n for i in range(n): for j in range(i): #첫번째 요소부터 i번째까지 위와 비교 if arr[i] > arr[j]: #뒤에 있는 요소(arr[i])가 크면 dp[i] = max(dp[i], dp[k]+1) 위 알고리즘의 시간복잡도는 O(n^2)을 갖게 됩니다. 시간복잡도를 개선하기 위해서는 이분탐색을 활용합니다. 주어진 배열..
Coding - Algo/알고리즘&자료구조 2021. 4. 4. 00:59
1