DP - LIS 최장증가부분수열

DP로 최장증가부분수열 구하기 Longest Increasing Subsequence python

 

방법은 두가지가 있다

하나는 이중 for문을 사용해서 o(n^2)

다른 하나는 이분탐색을 사용해서 o(nlogn)이 된다

 

 

1. o(n^2) 방법

dp배열: dp[i]를 포함한 LIS 길이 -> dp 배열 만들고 모두 1로 초기화로 시작

- 이중 for 문 -> 현재위치(i)와 이전에 있는 원소들 크기 비교

- 이전에 있는 원소가 작은경우 -> dp[i]와 dp[j]+1 중 더 큰것이 dp[i]

- dp배열의 최댓값이 LIS 길이

for i in range(len(arr)):
	for j in range(i):
    	if arr[j] < arr[i]:
        	dp[i] = max(dp[i], dp[j]+1)

 

 

2. o(nlogn) 방법 - 이분탐색(bisect) 활용

dp배열: 현재까지의 LIS(만들 수 있는 LIS 중 하나)

현재 값arr[i] 이 dp배열의 마지막 값보다 클 경우 -> dp에 append

그렇지 않으면 -> bisect 활용->현재값arr[i]이 dp배열의 어디에 들어갈지 찾음 -> dp배열 교체

 

for i in range(1, len(arr)):
	if dp[-1] < arr[i]:
    	dp.append(arr[i])
    else:
    	idx = bisect_left(dp, arr[i])
        dp[idx] = arr[i]