[알고리즘]동적계획법-LIS(최장증가부분수열)

최장증가부분수열의 개념 부분수열이라는 개념을 먼저 알아봅시다. 부분수열이란, 주어진 수열중 일부분을 뽑아 새로만든 수열을 말합니다.

이 때 순서가 섞이면 안됩니다. 순서가 섞인다는 의미는 원소들의 전후관계가 수열일때와 부분수열일때가 달라지는 것을 의미합니다.

최장증가 부분수열Long Increasing Subsequence이란, 부분수열의 원소가 오름차순을 유지하는 조건을 만족하고 이 중에서 길이가 가장 긴것을 말합니다. 수열을 하나 정의하고, 이를 기준으로 .부분수열과 최장증가 부분수열의 예를 보여드리겠습니다.

부분수열과 최장증가 부분수열을 설명하기 위한 수열 정의 위 수열을 기준으로, 부분수열 몇가지를 나타내면 아래와 같습니다. [표] 부분수열의 예 수열 {1,4,2}은 부분수열이 맞습니다.

전후관계가 바뀌지 않았고, 모든원소가 수열에 있는 원소 입니다. 수열 {1,3,5}은 부분수열이 맞습니다.

전후관계가 바뀌지 않았고, 모든원소가 수열에 있는 원소 입니다. 헷갈리실수 있는 부...