LIS 최장 증가 수열
예를들면 3 1 2 4 8 6 7 라는 배열이 있다면 가장 길게 증가하는순으로 정렬된 배열을 말한다 위 예제에선 1, 2, 4, 6, 7 이 가장 긴 증가 부분수열이다. DP를 이용해 손쉽게 n^2 시간으로 풀수있다. arr = [3, 1, 2, 4, 8, 6, 7] n = len(arr) dp = [1] * n for i in range(1, n): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) res = max(dp) 하지만 n의크기가 10만정도로 커진다면? 바로 nlgn 으로 풀수있는 알고리즘이 존재한다. 원리는 임의의 배열에 입력이 들어올때마다 정렬된 형태를 유지하며 가장 큰값보다 큰입력이 들어올경우 새로 추가하고 그것이..
더보기
