[BOJ] 11053번 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

LIS(Longest Increasing Subsequence)를 구하는 문제이다.
첫 통과한 코드는 다음과 같다.

dp[i]: i번째 index까지의 LIS의 최대길이

N = int(input())
nums = list(map(int,input().split()))
dp = [0 for _ in range(N)]
dp[0] = 1

for i in range(1,N):
  max_len = 0
  for j in range(0,i):
    if nums[j] < nums[i]:
      max_len = max(max_len,dp[j])
  dp[i] = max_len + 1
  
print(max(dp))

여기서 개선할 부분을 개선하면 다음과 같이 된다.

N = int(input())
nums = list(map(int,input().split()))
dp = [1 for _ in range(N)] # 하나만 있는 수열이면 길이 1이므로

for i in range(1,N):
  for j in range(0,i):
    if nums[j] < nums[i]:
      dp[i] = max(dp[i],dp[j]+1)
  
print(max(dp))

위 코드는 $O(N^2)$이어서 N 조건이 높아질 시 시간초과가 발생한다. 그때는 $O(NlogN)$으로 풀어야 하며, binary search를 이용해야 한다.

출처

dp = 가장 긴 증가하는 부분 수열을 저장할 배열
bisect.bisect_left(inc_arr, x): inc_arr가 정렬되어있다는 가정하에 x값이 들어갈 위치 반환

import bisect

x = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]]

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

print(len(dp))