DP - 가장 긴 증가하는 부분수열

Longest Increasing Subsequence (가장 긴 증가하는 부분 수열)

- 주어진 수열 내에서 가장 긴 부분 수열을 찾아내는 알고리즘

=> 중간에 감소하는 부분은 없다고 취급하고 생각

 

 

모든  0≤j<i 에  대해  D[i]=max(D[i],  D[j]+1)   if array[j]<array[i]​

 

​

부분 수열

- 원 수열의 항의 일부분만을 딴 수열

​

증가하는 부분 수열

- 부분수열 중 오름차순인 것

 

 

 

1. O(N^2) - 이중반복문

n = int(input())
num = list(map(int,input().split()))

dp = [1 for _ in range(n)] #증가하는 부분수열을 나타낸다.

for standard in range(1,n):
    for compare in range(standard):
        if num[standard] > num[compare]: # 증가하는 것이므로 비교(compare)값보다 클 경우로 생각한다.
            dp[standard] = max(dp[standard], dp[compare]+1)

print(max(dp))

 

 

 

2. O(NlogN) - 이진탐색

Lower Bound

- 원하는 값 k 이상이 처음 나오는 위치를 찾는 과정

- S원소 값을 보고 L배열에서 값을 비교한다.

- 오름차순 일 때 =+ 1

- 내림차순 일 때는 해당 자리 Lower_Bound

알고리즘

- 배열 = S(값이 들어있는 배열)

- 배열 = L(값이 없는 배열)

​

- S의 원소 < L의 맨 뒤 원소 경우 lower_bound를 찾아 그자리(L원소)에 S원소로 바꿔 버린다.

 

- len(L) <= 0, S의 원소 > L의 맨 뒤 원소 일 경우 L에 S원소 추가

​

 

 

 

 

< 좋은 자료 >

https://jason9319.tistory.com/113