DailyStudyNote

최장 증가 부분 수열 (LIS, Longest Increasing Sequence) 최장 증가 부분 수열(LIS) 란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거하여 부분 수열을 만들 수 있다. 이 때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 예를 들어, [6,2,5,1,7,4,8,3] 라는 수열이 존재하는 경우 LIS는 [2,5,7,8] 이 된다. [2,5], [2,7] 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 [2,5,7,8] 이기 때문이다. LIS(최장 증가 부분 수열)의 길이를 구하는 방법에는 두 가지가 있다. (1) DP(Dynamic Programing, 동적 계획법) - O(N^2) 알고리즘 (2) Lo..