최장 증가 부분 수열이란?
최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 수열에서 순서를 유지하며 값이 점점 커지는 가장 긴 부분 수열의 길이를 구하는 문제입니다. 예를 들어 [10, 9, 2, 5, 3, 7, 101, 18]의 LIS는 [2, 3, 7, 101]로 길이 4입니다(연속일 필요는 없습니다).
핵심 한 줄: "각 값으로 끝나는 가장 긴 증가 수열을 추적한다." 작은 풀이부터 보면 O(n²), 영리하게 보면 O(n log n)입니다.
풀이 1: O(n²) DP
dp[i] = i번째 원소로 끝나는 LIS의 길이.
dp[i] = max(dp[j] + 1) (단, j < i이고 arr[j] < arr[i])
각 i마다 앞쪽을 전부 보므로 O(n²)입니다. 직관적이고 LIS 복원도 쉽습니다.
풀이 2: O(n log n) — tails + 이분탐색
tails[k] = 길이가 k+1인 증가 부분 수열의 가능한 마지막 값 중 최솟값.
이 tails는 항상 증가하므로 이분탐색이 가능합니다. 새 값 x를 만나면
- •
tails에서x이상인 첫 위치를 이분탐색해 그 자리를x로 교체합니다. - •그런 위치가 없으면(=x가 가장 큼)
tails끝에 추가합니다.
마지막에 tails의 길이가 곧 LIS의 길이입니다. 더 작은 마지막 값을 유지할수록 뒤에 더 많은 값을 이어 붙일 수 있다는 것이 핵심 직관입니다.
동작 원리 (O(n log n))
1단계. 빈 tails 배열로 시작합니다.
2단계. 각 원소 x에 대해 tails에서 x가 들어갈 위치를 이분탐색합니다.
3단계. 그 위치에 값을 교체하거나, 끝이면 추가합니다.
4단계. 모든 원소를 처리한 뒤 tails의 길이가 답입니다.
알고노트 시각화는 새 값이 tails의 어느 칸을 교체/추가하는지 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 방법 | 시간 | 공간 |
|---|---|---|
| DP | O(n²) | O(n) |
| tails + 이분탐색 | O(n log n) | O(n) |
예시로 따라가기
[10, 9, 2, 5, 3, 7, 101, 18]:
- •tails 변화: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
- •최종 tails 길이 4 → LIS 길이 4
자주 하는 실수
- •tails를 실제 LIS로 착각: tails는 길이만 정확합니다. 실제 수열 복원은 별도 추적(인덱스 기록)이 필요합니다.
- •증가의 정의: 엄격한 증가(strict)면
lower_bound, 비감소 허용이면upper_bound를 써야 합니다. - •이분탐색 경계: 교체 위치를 잘못 잡으면 길이가 틀어집니다.
알고노트에서 직접 확인하세요
새 값이 들어올 때 tails 배열의 어느 위치가 교체되거나 늘어나는지 알고노트에서 단계별로 확인할 수 있습니다.