가장 긴 증가하는 부분 수열 (LIS)
LIS란
가장 긴 증가하는 부분 수열은 주어진 수열에서 순서를 유지하면서 증가하는 부분 수열 중 가장 긴 수열이다.
알고리즘 시각화
동작 예시
수열: [10, 20, 10, 30, 20, 50]
| 단계 | 현재 원소 | LIS 배열 | 설명 |
|---|---|---|---|
| 초기 | - | [] | 빈 배열 |
| 1 | 10 | [10] | 첫 원소 추가 |
| 2 | 20 | [10, 20] | 20 > 10, 뒤에 추가 |
| 3 | 10 | [10, 20] | 10 = LIS[0], 변화 없음 |
| 4 | 30 | [10, 20, 30] | 30 > 20, 뒤에 추가 |
| 5 | 20 | [10, 20, 30] | 20 = LIS[1], 변화 없음 |
| 6 | 50 | [10, 20, 30, 50] | 50 > 30, 뒤에 추가 |
결과: LIS 길이 = 4
교체가 발생하는 경우
수열: [10, 20, 30, 5, 15, 25, 35]
| 단계 | 현재 원소 | LIS 배열 | 설명 |
|---|---|---|---|
| 1-3 | 10, 20, 30 | [10, 20, 30] | 순서대로 추가 |
| 4 | 5 | [5, 20, 30] | 5 < 10, LIS[0] 교체 |
| 5 | 15 | [5, 15, 30] | 15 < 20, LIS[1] 교체 |
| 6 | 25 | [5, 15, 25] | 25 < 30, LIS[2] 교체 |
| 7 | 35 | [5, 15, 25, 35] | 35 > 25, 뒤에 추가 |
결과: LIS 길이 = 4
복잡도
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 시간 복잡도 | O(N log N) | N개 원소 × 이진 탐색 O(log N) |
| 공간 복잡도 | O(N) | LIS 배열 크기 |
주의사항
- LIS 배열은 실제 LIS가 아님: 각 길이별 최소 마지막 값만 저장
- 이진 탐색 방향: lower bound (이상)를 찾아야 함
- 증가 vs 비감소: 같은 값 허용 여부에 따라 이진 탐색 조건 조정
- 경로 복원: 별도 자료구조 필요 (이 방법으로는 길이만 구할 수 있음)
구현 팁
- 이진 탐색: lower bound 구현 (target 이상인 첫 위치)
- 위치 판단:
pos == size면 추가, 아니면arr[pos]교체 - 결과: 최종 배열의 크기가 LIS 길이
Last updated on