[알고리즘] 최장 증가 부분 수열(LIS) 알고리즘

• LIS(Longest Increasing Subsequence)란, 가장 긴 증가하는 부분 수열을 말한다.

• Q. 리스트 [6, 2, 5, 1, 7, 4, 8, 3]이라는 배열이 존재한다. 이 배열의 LIS를 구해라.

• A. [2, 5, 7, 8]

• Code

import sys
input = sys.stdin.readline

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

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

• 위의 알고리즘의 시간복잡도는 O(N^2)가 됩니다.
• 탐색범위가 넓어질수록 위의 코드를 사용하기에는 무리가 있습니다. 시간복잡도를 개선하기 위해서는 이분 탐색을 활용합니다.

import sys
input = sys.stdin.readline

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

for i in A:
    if memoization[-1] < i:
        memoization.append(i)
    else:
        left = 0
        right = len(memoization)
        while True:
            if left >= right:
                break
            mid = (left + right) // 2
            if memoization[mid] > i:
                left = mid + 1
            else:
                right = mid
        memoization[right] = i
print(len(memoization) - 1)

Q1. 이분 탐색은 정렬이 수행된 데이터에 한해서 이루어지는 작업인데 이 코드에는 정렬이 수행된 부분이 없는데도 이 논리를 어떻게 적용할 수 있는지?