AlgoStruct/Algorithm

LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 [Python]

🐭LIS(Longest Increasing Subsequence)란? 어떠한 수열이 있을 때, 수열의 원소 중 일부를 뽑아내여 새로 만든 수열을 부분 수열이라고 합니다. 이때 이 부분 수열이 오름차순을 지키면서, 부분 수열 중 길이가 최대인 경우 해당 부분 수열을 LIS, 최장 증가 부분 수열이라고 합니다. 아래와 같은 길이가 6인 수열이 있다고 해봅시다. 이 수열에서 증가하는 부분 수열들은 [10, 20], [10, 30], [10, 20, 30] ... 등 여러가지가 있을겁니다. 이 부분 수열들 중에 가장 긴 수열은 [10,20,30,50] 입니다. 그렇다면 어떤 방식으로 LIS를 찾을 수 있을까요? https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 ..