문제

어떠한 리스트가 주어질 때, 연속해서 가장 긴 증가하는 수열의 개수를 구하라
[7,3,6,2,8,5,9,4] => [3,6,8,9]

풀이

LIS 알고리즘을 이용한다.
(Longest increasing Subsequence)

dp = [] 를 만들고
리스트의 숫자를 하나씩 확인해 맨 뒤의 수보다 크다면 추가, 작거나 같으면 그 숫자가 dp에 어느 위치에 들어갈지 정해주면 된다.

이중 for문을 이용하면 가볍게 풀수 있다 하지만 O(n^2)의 시간 복잡도를 갖기 때문에 N이 100만 일 경우는 시간 초과가 나게 된다.

시간 복잡도를 해결하기 위해 이분탐색을 이용한다.

N = int(input())
num_list = list(map(int,input().split()))

dp = [0]
# [10,20,10,30,20,50]
for num in num_list :
  if num > dp[-1]:
    dp.append(num)
  else:
    left = 0
    right = len(dp)
    
    while left < right:
      mid = (left+right)//2
      if dp[mid] < num:
        left = mid+1
      else:
        right = mid
    dp[right] = num

print(len(dp)-1)

[100, 50, 70, 90, 75, 87, 105, 78, 110, 60] 이 배열의 LIS를 구한다고 가정해보면,

LIS는 [50, 70, 75, 87, 105, 110] 로, 길이는 6이 된다.

아래와 같은 순서로 진행된다.

[0] 
[0, 100]
[0, 50]
[0, 50, 70]
[0, 50, 70, 90]
[0, 50, 70, 75]
[0, 50, 70, 75, 87]
[0, 50, 70, 75, 87, 105]
[0, 50, 70, 75, 78, 105]

[0, 50, 70, 75, 78, 105, 110]
[0, 50, 60, 75, 78, 105, 110]

0을 뺀 나머지의 길이를 구하면 LIS의 길이가 된다.

참고 : https://jainn.tistory.com/90

숫자가 정렬된다. 실제 LIS의 값과는 다르다.
수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 최적의 위치가 앞에 있을 수도 있기 때문이다.
개수만 구하면 되는 문제기 때문에 이렇게 답을 도출해낸다.

(그나저나 LIS의 값은 어떻게 구해야하나.. )