[DP] 가장 긴 증가하는 부분 수열(LIS)의 구현 방법, 활용 백준 문제 모음

가장 긴 증가하는 부분 수열 LIS의 구현 방법

LIS의 구현 방법에는 기본 DP를 활용하는 방법과 Binary Search를 활용하는 방법이 있다. 만약 N이 O(N^2)로 처리할 경우 시간 초과가 날 만큼 크다면 반드시 Binary Search를 이용해서 풀어야 한다.

 

1. DP로만 풀이

n = int(input())
array = list(map(int, input().split()))
dp = [1 for _ in range(n)]
for i in range(1,n):
    for j in range(i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

2. Binary Search로 풀이

import bisect
n = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]
for i in range(1, n):
    idx = bisect.bisect_left(dp, arr[i])
    if idx == len(dp):
        dp.append(arr[i])
    else:
        dp[idx] = arr[i]
print(len(dp))

 

LIS 활용 백준 문제 모음

• 11053 가장 긴 증가하는 부분 수열 
• 2352 반도체 설계
• 12015 가장 긴 증가하는 부분 수열 2 
• 14003 가장 긴 증가하는 부분 수열 5
• 25665 전깃줄