LIS (최장 증가 부분 수열, Longest Increasing Subsequence)

LIS (최장 증가 부분 수열, Longest Increasing Subsequence)

주어진 수열에서 원소의 순서를 유지하면서 값이 증가하는 가장 긴 부분 수열을 찾는 문제로, DP O(n²) 또는 이분 탐색 O(n log n)으로 해결

목적: 부분 수열 최적화, 정렬 관련 문제, DP 학습

특징: 부분 수열(연속 아님), 순서 유지, 증가 조건, DP 대표 문제

예시: [10, 20, 10, 30, 20, 50] → LIS = [10, 20, 30, 50], 길이 = 4

DP 풀이 O(n²)

• •dp[i] = arr[i]로 끝나는 LIS 길이
• •dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
• •초기값: dp[i] = 1 (자기 자신만)
• •답: max(dp[i])

이분 탐색 풀이 O(n log n)

• •tail[i] = 길이 i+1인 LIS의 마지막 원소 중 최솟값
• •각 원소에 대해 이분 탐색으로 tail 갱신
• •tail 배열은 항상 정렬 상태 유지
• •답: tail 배열의 길이

동작(이분 탐색)

시간 복잡도: DP O(n²), 이분 탐색 O(n log n)

공간 복잡도: O(n)

LIS 복원: 이분 탐색에서 parent 배열로 역추적

장점: DP 기초 문제, 다양한 응용, 효율적 풀이 가능

단점: 실제 수열 복원 추가 작업 필요

적용사례: 박스 쌓기, 스케줄링, 최장 체인, 러시안 인형

비교: LIS(증가) vs LCS(공통) vs LDS(감소)

연관: 동적 프로그래밍, 이분 탐색, 부분 수열, 최적화