[Python]가장 긴 증가하는 부분 수열(LIS) 길이 구하는 방법 2가지

가장 긴 증가하는 부분 수열(LIS) 풀이 방법

부분 수열 : 임의의 수열이 주어질 때, 몇 개의 수를 제거하여 만든 수열
부분 수열 중 가장 긴 증가하는 부분 수열을 구하는 방법은 2가지가 있다.

1. DP(Dynamic Programming) - 동적 계획법

2. Binary Search - 이분 탐색

1. 동적 계획법을 사용한 풀이 (백준 11053)

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

import sys
input = sys.stdin.readline

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

dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i] = max(dp[i],dp[j]+1)

print(max(dp))

dp: arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

현재 위치(i)의 원소 vs 이전에 있는 원소(j)

- 작다면 증가하는 부분 수열이 될 수 있기 때문에 dp값 설정

- dp값 : 현재 위치의 이전 숫자 중 최대 dp 값 + 1 (현재 값 추가하므로)

이렇게 dp를 통해 문제를 풀면 시간복잡도는 O(N^2)..

2. 이분 탐색을 사용한 풀이 (백준 12015)

해당 문제에서, n의 범위가 늘어났기 때문에 dp로 풀면 당연히 시간초과가 난다..!
따라서 이분탐색으로 풀이해야 한다..

import sys
input = sys.stdin.readline

def bs(arr,target):
    left, right = 0, len(arr)-1
    while left<= right:
        mid = (left+right)//2
        if arr[mid]<target:
            left = mid+1
        else:
            right = mid-1
    return left


n = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]
for i in range(n):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bs(dp,arr[i])
        dp[idx] = arr[i]

print(len(dp))

dp : 가장 긴 증가하는 부분 수열을 저장하는 배열

현재 위치(i)의 원소 vs 이전 원소들

1. 현재 위치 원소가 더 크면 dp에 추가 (dp[-1]은 이전 원소들의 최댓값)

2. 더 작거나 같으면,, 이분 탐색을 통해 dp에 특정 값이 들어갈 위치를 찾고 arr[i]로 바꿔주기

3. dp의 길이 == 가장 긴 증가하는 부분 수열의 길이

cf) bisect 라이브러리를 사용해도 되지만, 나는 bisect 라이브러리 없이 구현하여 사용하였다.

이때 시간 복잡도는..? O(NlogN)이다

가장 긴 증가하는 부분 수열 자체를 구하는 방법은???

https://bskwak.tistory.com/260

[Python] 가장 긴 증가하는 부분 수열(LIS) 풀이 방법