최장증가부분수열 - LIS(Longest Increasing Subsequendce)

최장증가 부분수열 - LIS(Longest Increasing Subsequendce) 주어진 수열에서 일부 원소를 골라내어 만든 부분 수열 중, 오름차순으로 정렬된 가장 긴 부분수열을 의미한다. 이때 핵심은 부분수열이 반드시 연속될 필요는 없다는 것이다. 즉 몇 개의 원소를 건너뛰어도 해당 연속으로 정렬만 되면 된다는 것이다. 예를 들어 {2, 3, 8, 6, 4, 5, 9, 1}의 경우 가장 긴 증가 부분수열은 {2, 3, 4, 5, 9}이 됨 특징부분수열의 각 원소는 원래 수열에서 순서를 지켜야 함, 연속적일 필요는 없음오름차순이므로 앞의 원소보다 뒤의 원소가 크거나 같아야 함한 수열에는 여러 개의 최장 증가 부분 수열이 존재할 수 있음 구하는 방법동적계획법 - DP각 인덱스에서 끝나느 LIS의 길..

2025.05.07