빠른 비교
| 방식 | 시간 | 장점 |
|---|---|---|
| O(N²) DP | O(N²) | 의미가 직관적이고 복원 쉬움 |
| tails + binary search | O(N log N) | 길이만 빠르게 계산 |
| parent 복원 | O(N log N) + 추적 배열 | 실제 수열 복원 |
| lower bound | 같은 길이의 끝값을 더 작게 유지 | 엄격 증가 기준 |
csharp
var tails = new List<int>();
foreach (int value in arr)
{
int index = LowerBound(tails, value);
if (index == tails.Count) tails.Add(value);
else tails[index] = value;
}구조
LIS는 원래 배열의 순서를 유지하되, 선택한 값들이 증가하도록 만드는 가장 긴 부분 수열입니다. 연속된 구간일 필요는 없습니다.
O(N²) DP에서는 dp[i]를 i번째 원소를 마지막으로 하는 LIS 길이로 둡니다.
csharp
int[] dp = Enumerable.Repeat(1, n).ToArray();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[j] < arr[i])
{
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
}O(N log N) 방식의 tails[len]은 길이가 len + 1인 증가 부분 수열의 가능한 가장 작은 끝값입니다. 실제 수열 자체를 바로 뜻하지는 않습니다.
이분 탐색 기준
엄격 증가 LIS에서는 현재 값 이상이 처음 나오는 위치를 찾아 교체합니다. 같은 값을 허용하지 않기 위해 lower bound를 씁니다.
csharp
int LowerBound(List<int> values, int target)
{
int left = 0;
int right = values.Count;
while (left < right)
{
int mid = (left + right) / 2;
if (values[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}비감소 부분 수열이 필요하다면 같은 값을 뒤에 붙일 수 있어야 하므로 upper bound 기준으로 바뀝니다. 문제에서 “증가”인지 “감소하지 않음”인지 먼저 확인해야 합니다.
주의할 점
tails 배열은 길이 계산을 위한 압축 상태입니다. 중간 값들이 실제 원래 배열에서 하나의 유효한 부분 수열을 이룬다고 가정하면 안 됩니다. 실제 수열을 출력해야 하면 이전 인덱스와 각 길이의 마지막 인덱스를 별도로 저장하세요.
입력 크기가 작으면 O(N²) DP가 더 명확합니다. N이 1,000 정도면 충분할 수 있지만, N이 100,000이면 O(N log N) 방식이 필요합니다.
참고 링크
1 sources