[CS 지식 - 알고리즘] 최장 증가 부분 수열(LIS)
1. 최장 증가 부분 수열 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열 부분 수열 : 어떤 수열이 주어질 떄, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열의 부분 수열 증가 부분 수열 : 부분수열이 오름차순을 유지하는 것 LIS : 어떤 수열에서 만들 수 있는 부분 수열 중 가장 길면서 오름차순을 유지하는 수열 예시) 위와 같은 길이가 8인 수열이 주어진다고 가정 이 수열에서 증가하는 부분 수열을 뽑는다면 다음과 같이 여러 수열이 나올 것 [2, 3], [1, 3], [2, 5],[2, 3, 5],[1, 3, 5]등등 ▶ 이중 가장 긴 수열은 [2, 3, 5, 6, 7] 물론 [1, 3, 5, 6, 7..
