[TIL] LIS 알고리즘 (최장 증가 부분 수열)
최장 증가 부분 수열(LIS, Longest Increasing Subsequence) - 원소가 n개인 배열의 일부 원소로 만든 수열 중 각 원소가 이전의 원소보다 크며 길이가 최대인 부분 수열 백준 dp 알고리즘을 풀다가 LIS 알고리즘을 접하게 되었다. LIS를 푸는 방법으로는 DP를 이용한 방법과 이분탐색 방법 두 가지가 있다. 1.DP를 활용 [1,3,2,7,6,4,9,8] 이라는 배열 lst가 존재할 때 dp 리스트를 사용하여 각 인덱스별로 최장 증가 부분 수열의 길이를 구한 것이다. lst =[1,3,2,7,6,4,9,8] dp=[1]*len(lst) for i in range(len(lst)): for j in range(i): if lst[i]>lst[j]: dp[i] = max(dp[i..
