Quick Comparison
| 방식 | 시간 | 장점 |
|---|---|---|
| O(N²) DP | O(N²) | 의미가 직관적이고 복원 쉬움 |
| tails + binary search | O(N log N) | 길이만 빠르게 계산 |
| parent 복원 | O(N log N) + 추적 배열 | 실제 수열 복원 |
| lower bound | 같은 길이의 끝값을 더 작게 유지 | 엄격 증가 기준 |
int[] values = { 10, 9, 2, 5, 3, 7, 101, 18 };
List<int> lis = LongestIncreasingSubsequence(values); // 2, 3, 7, 18
int length = lis.Count;길이만 필요하면 tails와 이분 탐색으로 O(n log n)을 선택합니다. 실제 수열도 필요하면 각 원소의 이전 index를 추가로 기록해야 합니다.
구조
LIS는 원래 배열의 순서를 유지하되, 선택한 값들이 증가하도록 만드는 가장 긴 부분 수열입니다. 연속된 구간일 필요는 없습니다.
O(N²) DP에서는 dp[i]를 i번째 원소를 마지막으로 하는 LIS 길이로 둡니다.
static int LongestIncreasingLengthQuadratic(IReadOnlyList<int> values)
{
var dp = Enumerable.Repeat(1, values.Count).ToArray();
for (int i = 0; i < values.Count; i++)
{
for (int j = 0; j < i; j++)
{
if (values[j] < values[i])
{
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
}
return dp.Length == 0 ? 0 : dp.Max();
}O(N log N) 방식의 tails[len]은 길이가 len + 1인 증가 부분 수열의 가능한 가장 작은 끝값입니다. 실제 수열 자체를 바로 뜻하지는 않습니다.
실제 수열 복원
각 길이의 마지막 원본 index와 그 앞 원본 index를 함께 기록하면 O(N log N)으로 길이와 수열을 모두 얻습니다. 빈 배열은 빈 수열을 반환합니다.
static List<int> LongestIncreasingSubsequence(int[] values)
{
var tailValues = new List<int>();
var tailIndices = new List<int>();
int[] previous = Enumerable.Repeat(-1, values.Length).ToArray();
for (int i = 0; i < values.Length; i++)
{
int position = LowerBound(tailValues, values[i]);
if (position > 0) previous[i] = tailIndices[position - 1];
if (position == tailValues.Count)
{
tailValues.Add(values[i]);
tailIndices.Add(i);
}
else
{
tailValues[position] = values[i];
tailIndices[position] = i;
}
}
var result = new List<int>();
for (int index = tailIndices.Count == 0 ? -1 : tailIndices[^1]; index != -1; index = previous[index])
{
result.Add(values[index]);
}
result.Reverse();
return result;
}이분 탐색 기준
엄격 증가 LIS에서는 현재 값 이상이 처음 나오는 위치를 찾아 교체합니다. 같은 값을 허용하지 않기 위해 lower bound를 씁니다.
static int LowerBound(IReadOnlyList<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가 더 명확합니다. 허용 범위는 언어·시간 제한·상수 비용에 따라 달라지므로, 입력 크기와 제한을 함께 계산해 O(N log N) 방식으로 전환하세요.
참고 링크
1 sources