들어가며 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence; LIS)은 DP로 풀 수 있는 유명한 문제 유형 중 하나입니다. 문제의 핵심은 주어진 시퀀스에서 오름차순으로 정렬된 가능한 가장 긴 부분 수열을 찾는 것 입니다. 참고로 답이 되는 부분 수열은 꼭 하나가 아니라 여러 개가 될 수도 있습니다. 이 문제를 푸는 방법은 크게 두 가지가 알려져 있습니다. DP로만 풀기 와 DP + 이분탐색으로 풀기 입니다. 각각 O(n²)와 O(n log(n))의 시간복잡도를 가집니다. n이 작으면 전자의 방법으로도 충분할 수 있지만 n이 더 커지면 힘들겠죠. 풀어볼 문제는 가장 긴 증가하는 부분 수열5 입니다. 문제는 아주 짧고 명확합니다. 예를 들어 수열 A가 A = {10,