LIS(최장증가 부분 수열)
by 모나 | TECH_ESSAY | 2025-12-21
#알고리즘 #동적계획법 예외 케이스 스스로 생각할 수 있어야 함. dp[i] 정의: i까지의 수열 중 가장 길게 증가하는 부분 (i를 포함한다)-->포함하든 안하든 답은 상관 없는데 주로 포함하는걸로 <점화식> dp[i] = 1 dp[i] = max(dp[j] + 1) (j < i && arr[j] < arr[i]) dp : O(n^2) dp[] 배열의 최댓값을 구하면 됨 1~i까지 중 0~i-1까지 중 이분탐색 : O(nlogn), 오름차순 정렬된 상태에서 가능한 이분탐색 -> 새로운 수열 b[] 선언. b[len]: 길이가 len인 lis의 마지막 값...