최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 효율적인 풀이 방법은?
보통 freeCodeCamp해설
LIS 문제는 단순 DP로 O(n²)에 풀 수 있지만, 보조 배열과 이진 탐색(lower_bound)을 활용하면 O(n log n)에 최적화할 수 있습니다. 보조 배열의 각 위치에 해당 길이의 증가 수열에서 가능한 가장 작은 마지막 값을 유지하여 효율적으로 탐색합니다.
LIS 문제는 단순 DP로 O(n²)에 풀 수 있지만, 보조 배열과 이진 탐색(lower_bound)을 활용하면 O(n log n)에 최적화할 수 있습니다. 보조 배열의 각 위치에 해당 길이의 증가 수열에서 가능한 가장 작은 마지막 값을 유지하여 효율적으로 탐색합니다.