dynamic programing
-
[Algorithm] - LIS(최장 증가 부분 수열)Algorithm/Algorithm 2022. 9. 5. 13:57
LIS 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열 E.g) [3, 5, 7, 9, 2, 1, 4, 8] 부분 수열 -> [3, 7, 9, 1, 4, 8] / [3, 5, 7, 8] / [1, 4, 8] 길이가 길면서 원소가 증가하는 최장 부분 수열-> [3,5,7,8] 알고리즘 1. DP 각 원소를 돌면서 현재 원소보다 작은 값들(DP) 중 가장 큰 값에다가 연결 각 원소를 돌때마다 하위 원소들에 대해서 완전 탐색이 필요하여 O(N^2) 시간 복잡도 #Init dp = [0]*(n+1); for i in range(n) : for j in range(i) : dp[i] = max(d..