목록LIS (1)

Young

LIS(longest increasing sequence) - O(NlogN)

오늘은 DP의 특별한 문제 형태라고 할 수 있는 LIS를 알아보겠습니다.보통의 DP로 풀게 되면 O(N^2)으로 풀게 됩니다. 하지만 N의 값이 커지면 O(NlogN)의 알고리즘이 필요합니다. 우선 LIS 문제 정의 부터 알아보겠습니다. The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is..
algorithm 2019. 2. 14. 17:20
이전 Prev 1 Next 다음