최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다. 아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다. 이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자. 다이나믹 프로그래밍을 이용한 방법 : O(N^2) 이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다. 하지만 수열에 존재하는 수의 개수가 k개일 때,..