Concept 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 아래와 같은 수열이 있을 때 오름차순으로 정렬된 부분 수열은 1,3,5 1,3,4 3,5 1,2,4 등과 같이 존재하며, 해당 수열에서 최장 증가 부분 수열은 3 Feature 이러한 LIS의 길이를 구하는 방법 중 단순한 접근법은 Brute-Force방법으로 수열의 총 길이가 K라고 가정할 때 1개 이상의 원소를 가지는 모든 부분수열의 경우의 수는 2^K개로 모든 부분 수열의 오름차순 정렬을 확인하는 것은 시간이 매우 오래 걸린다. LIS의 길이를 구하는 최적 방법에는 2가지가 있다. 다이나믹 프로그..