Longest Increasing Subsequence에 대해 설명하세요
Keyword
DP, 오름차순, 부분 수열, 이분 탐색
Script
LIS 문제는 DP를 이용해 빠르게 해결할 수 있는 대표적인 문제입니다. 특정 수열이 주어졌을때, 해당 수열의 부분 수열 중 오름차순으로 이루어진 부분 수열들이 있습니다. 그 중에서 가장 긴 부분 수열을 찾는 것이 이 문제의 목표입니다.
먼저 수열의 길이와 동일한 DP 배열을 만들고, 처음부터 끝까지 탐색합니다. 이때, 각 탐색에서는 해당 위치 이전의 값들을 살펴보고 만약 더 작은 값이 있다면, 해당 값의 DP 배열의 값에 1을 더해 결과로 가져옵니다. 이 결과 중 가장 큰거나 같은것을 해당 위치 DP 배열의 값으로 저장합니다. 이러한 방식을 사용하면, O(N^2)의 시간복잡도로 수행됩니다.
LIS의 길이만 구하는 것이라면, 이분 탐색을 적용하여 시간복잡도는 O(NlogN)으로 줄일 수 있습니다. 먼저 빈 LIS 배열을 선언하고 수열의 첫번째 원소를 넣어줍니다. 그리고 이후 수열의 값을 탐색하면서, 만약 LIS 배열의 마지막 값보다 수열의 값이 크다면 LIS 배열에 값을 넣어주고, 만약 수열의 값이 더 작다면 이분 탐색을 이용해서 해당 값보다 처음으로 큰 값이 나오는 곳(lower_bound)에 존재하는 값과 교체를 합니다.
위 방식을 통해 빠르게 LIS의 길이를 구할 수 있고, 이는 순회 과정 속의 탐색 과정을 이분 탐색으로 개선했기 때문에 더 빠른 시간복잡도를 가집니다.
Additional
python 코드
O(N^2)
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1]*n
for cur in range(1, n):
for front in range(0, cur):
if arr[front] < arr[cur]:
dp[cur] = max(dp[cur], dp[front]+1)
print(max(dp))O(NlogN)
import sys, bisect
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
inc_arr = [sys.maxsize]*n
for i in range(0,n):
idx = bisect.bisect_left(inc_arr, arr[i])
inc_arr[idx] = arr[i]
print(bisect.bisect_left(inc_arr, sys.maxsize))LIS O(nlogn)
with programming