[Algorithm] - LIS(최장 증가 부분 수열)

LIS

---

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열

• E.g) [3, 5, 7, 9, 2, 1, 4, 8]
• 부분 수열 -> [3, 7, 9, 1, 4, 8] / [3, 5, 7, 8] / [1, 4, 8] 
• 길이가 길면서 원소가 증가하는 최장 부분 수열-> [3,5,7,8]

 

알고리즘

---

1. DP

각 원소를 돌면서 현재 원소보다 작은 값들(DP) 중 가장 큰 값에다가 연결

• 각 원소를 돌때마다 하위 원소들에 대해서 완전 탐색이 필요하여 O(N^2) 시간 복잡도

#Init
dp = [0]*(n+1);
for i in range(n) :
  for j in range(i) :
    dp[i] = max(dp[i], dp[j] + 1)
   
max(dp)

 

2. 이분탐색

---

• DP로 구현 하는 것보다 더 빠르게 구현하는 방법
• 시간 복잡도 : O(NlogN) N개에 대해서 이분탐색

모든 범위를 살펴보는 것이 아닌, 현재 연결되어 있는 부분 수열에서 계속하여 갱신하여 처리

#BOJ 12015번

datas = list(map(int,input().split()))
dp = [datas[0]]

for data in datas :
    if data > dp[-1] :
        dp.append(data)
    else :
        dp[bisect.bisect_left(dp , data)] = data
        
print( len(dp) )