최장 증가 부분 수열(LIS)

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

18353번: 병사 배치하기

이번엔 문제를 푸는 두가지 유형을 통해 풀이를 점검해보려 한다.

 

랜덤으로 배치된 수열에서 가장 길게 증가하는 수열을 구하는 문제이다.

 

이때 O(n^2)을 가지는 기본 DP를 활용한 방법은 i 번까지 확인하면서 i번전까지 만족하던거중 가장높은거 +1을 하는방법이다.

import sys
input = sys.stdin.readline

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

d = [1] * n
for i in range(n):
  for j in range(i):
    if data[i]<data[j]:
      d[i] = max(d[i],d[j]+1)

print(n-max(d))

 그 후 dp에서 가장 높은것이 최장수열이기 때문에 전체에서 빼주면 빼야하는 수의 개수가 나온다.

 

하지만 이는 O(n^2)이기 때문에 bisect를 활용한 O(nlogn)이 방법이 있다.

import sys
input = sys.stdin.readline

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

arr = arr[::-1]
dp = [1e7]*n
from bisect import bisect_left
for i in arr:
	dp[bisect_left(dp,i)] = i

print(dp.count(1e7))

계속해서 bisect를 통해 자리에 배정해 주는데 이때 계속 증가한다면 계속 맨 오른쪽에 추가될 것이고, 아니라면 중간에 있었던 것 대신 갱신되기 때문에, O(nlogn)만으로 최장증가부분수열을 만들 수 있다.