Note
**LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)**는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다. 동적 프로그래밍을 활용하여 해결할 수 있습니다.
LIS란?
**LIS(Longest Increasing Subsequence)**는 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다.
부분 수열 (Subsequence)
부분 수열은 원본 수열에서 일부 원소를 선택하되, 원래 순서를 유지하는 수열입니다.
예시:
- 원본 수열:
[10, 20, 10, 30, 20, 50] - 부분 수열:
[10, 20, 30, 50]✓ (순서 유지) - 부분 수열:
[20, 10, 30]✗ (순서 위반)
증가하는 부분 수열
부분 수열의 각 원소가 이전 원소보다 큰 경우:
[10, 20, 30, 50]✓ (증가)[10, 20, 10, 30]✗ (감소 구간 포함)
LIS 문제의 정의
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하시오.
예시:
- 수열:
[10, 20, 10, 30, 20, 50] - LIS:
[10, 20, 30, 50]또는[10, 20, 30, 50] - 길이: 4
동적 프로그래밍 접근법 (O(n²))
핵심 아이디어
dp[i]: i번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 길이
점화식
dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]의미:
- i번째 원소보다 작은 모든 이전 원소 j에 대해
- j를 마지막으로 하는 부분 수열에 i를 추가할 수 있음
- 그 중 가장 긴 것에 1을 더한 값이
dp[i]
초기 조건
모든 원소는 최소한 자기 자신만으로 길이 1의 부분 수열을 만들 수 있습니다:
dp[i] = 1 for all i구현
def lis_dp(arr):
n = len(arr)
dp = [1] * n # 모든 원소는 최소 길이 1
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) # 모든 dp[i] 중 최댓값시간 및 공간 복잡도
시간 복잡도
- O(n²): 각 원소 i에 대해 모든 이전 원소 j를 확인
- n이 작을 때 (n ≤ 1,000) 충분히 빠름
공간 복잡도
- O(n): dp 배열만 필요
알고리즘 동작 과정
예시: [10, 20, 10, 30, 20, 50]
단계별 계산:
| i | arr[i] | j | 조건 | dp[j] | dp[i] |
|---|---|---|---|---|---|
| 0 | 10 | - | - | - | 1 |
| 1 | 20 | 0 | 20 > 10 | 1 | max(1, 1+1) = 2 |
| 2 | 10 | 0,1 | 10 > 10? 10 > 20? | - | 1 |
| 3 | 30 | 0,1,2 | 30 > 10, 30 > 20, 30 > 10 | 1,2,1 | max(1, 1+1, 2+1, 1+1) = 3 |
| 4 | 20 | 0,1,2,3 | 20 > 10, 20 > 20?, 20 > 10, 20 > 30? | 1,2,1,3 | max(1, 1+1, 2+1, 1+1) = 3 |
| 5 | 50 | 0,1,2,3,4 | 50 > 10, 50 > 20, 50 > 10, 50 > 30, 50 > 20 | 1,2,1,3,3 | max(1, 1+1, 2+1, 3+1, 3+1) = 4 |
최종 dp 배열: [1, 2, 1, 3, 3, 4]
LIS 길이: max(dp) = 4
최적화된 방법 (O(n log n))
더 큰 n에 대해서는 이진 탐색을 활용한 O(n log n) 방법이 있습니다:
def lis_binary_search(arr):
import bisect
dp = []
for num in arr:
pos = bisect.bisect_left(dp, num)
if pos == len(dp):
dp.append(num)
else:
dp[pos] = num
return len(dp)핵심 아이디어:
dp[i]: 길이 i+1인 증가하는 부분 수열의 마지막 원소의 최솟값- 이진 탐색으로 적절한 위치를 찾아 업데이트
시간 복잡도: O(n log n)
LIS의 활용
1. 기본 LIS 문제
주어진 수열의 LIS 길이를 구하는 문제
2. 변형 문제
- 가장 긴 감소하는 부분 수열 (LDS): 수열을 뒤집어 LIS 적용
- 가장 긴 바이토닉 부분 수열: 증가 후 감소하는 부분 수열
- LIS를 구성하는 원소 출력: 역추적(traceback) 필요
주의사항
1. 부분 수열 vs 부분 배열
- 부분 수열 (Subsequence): 원소를 건너뛸 수 있음, 순서 유지
- 부분 배열 (Subarray): 연속된 원소만 선택
LIS는 부분 수열을 다룹니다.
2. 중복 원소 처리
원본 수열에 중복이 있을 수 있지만, 증가하는 부분 수열에서는 중복이 없어야 합니다.
3. dp 배열의 의미
dp[i]는 i번째 원소를 포함하는 부분 수열의 최대 길이입니다.
따라서 최종 답은 max(dp)입니다.
관련 알고리즘
- 동적 프로그래밍 (Dynamic Programming)
- 이진 탐색 (Binary Search)
- BOJ 11053: 가장 긴 증가하는 부분 수열 - 기본 LIS 문제