LIS 최장 증가 부분 수열

1. Dynamic Programming (동적 계획법)

array = [5, 2, 1, 4, 3, 5]
dp = [1 for _ in range(len(array))] 

for i in range(1, len(array)):
    for j in range(i): # array의 처음부터 i-1번째 인덱스까지
        if array[i] > array[j]: # 숫자의 크기를 비교하여 현재 값이 더 크면
            dp[i] = max(dp[i], dp[j] + 1) # dp 배열의 값을 더 큰 값으로 갱신

1. Binary Search (이분 탐색)

from bisect import bisect_left

array = [5, 2, 1, 4, 3, 5]
dp = [1]
x = [array[0]]

for i in range(1, len(array)):
    if array[i] > x[-1]: # 현재 값이 x 배열의 마지막 값보다 클 경우
        x.append(array[i]) # x 배열에 현재 값을 추가해 주고
        dp.append(dp[-1] + 1) # 증가 부분 수열의 길이를 1 증가시킨다.
    else: # 그렇지 않을 경우
        idx = bisect_left(x, array[i]) # 현재 값이 x 배열의 몇 번째 인덱스에 들어갈 수 있는지를 찾아서
        x[idx] = array[i] # x 배열의 idx 위치에 현재 값을 넣어준다.

 

참고 페이지:https://one10004.tistory.com/217

[Algorithm] 최장 증가 부분 수열 (LIS)