longest increasing subsquence

최장 증가 수열 (LIS, Longest Increasing Subsquence)

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