📖 LIS (Longest Increasing Subsequence)

한국어로 해석하면 최장 증가 부분 수열,
부분 수열이 주어진 수열에서 일부 항들을 원래 순서대로 나열하여 얻는 수열을 부분 수열 이라고 한다.
그렇다면, 최장 증가 부분 수열은 부분 수열 중에서도 가장 길이가 긴 부분 수열을 말한다.

그렇다면, LIS를 어떻게 구현할 것인지를 생각해야하는데, LIS를 구현하는 방법은 크게 두가지로 구분하려고 한다.

📌 다이나믹 프로그래밍 이용

LIS는 다이나믹 프로그래밍 방법을 이용하여 문제를 해결 할 수 있다.

dp = []
test1 = [1,3,5,6,8,9,2,4]
for i in range(len(test1)):
    dp.append(1)
    for j in range(i):
        if test1[j] < test1[i]:
            dp[i] = max(dp[i],dp[j]+1)

print(dp)

첫 반복문을 통해 수열의 각 원소를 순회한다. 그리고 각 원소를 순회 할 때 마다 반복문을 순회하는데 이 때 순회하는 반복문은 해당 원소 이전의 수보다 큰지 작은지를 파악한다. 이전의 수보다 작다면 해당 수열의 위치는 1로 고정하고, 이전의 수열보다 크다면 계속 1씩 증가하도록 구현한다면 해당 기록용 리스트의 최대 값이 최장 부분 수열의 길이가 된다.

다이나믹 프로그래밍 방식을 이용하여 문제를 해결한다면 N^2의 속도를 가지게 되어 수열의 길이가 길어진다면 소요되는 시간 또한 증가하게 된다. 그렇다면, 시간 소모를 줄일 필요가 있는데 시간 소모를 줄이기 위해서 이진 탐색 방식을 이용하여 문제를 해결할 수 있다.

📌 이진 탐색 이용

from bisect import bisect, bisect_left


dp = []
test1 = [1,3,5,6,8,9,2,4]
for i in range(len(test1)):
    if len(dp) == 0:
        dp.append(test1[i])
        continue
    if dp[-1] < test1[i]:
        dp.append(test1[i])
    else:
        dp[bisect_left(dp,test1[i])] = test1[i]

앞에서 살펴봤듯이 다이나믹 프로그래밍을 이용하여 LIS 문제를 해결하는데는 시간이 너무 오래걸리는 점을 살펴봤다. 오래걸리는 이유를 조금 더 자세하게 살펴보면 원소 하나씩 이전의 수열 전체를 살펴보기 때문에 오래 걸린다. 그렇다면 전체를 살펴보지 않으면 해결이 가능할 것이다.
하나씩 전체를 살펴보는 방법 대신 이진 탐색을 이용하여 부분 탐색을 시도한다. 예를 들어 리스트의 마지막 값이 현재 살펴보는 원소의 값보다 작다면 리스트의 마지막에 추가, 그렇지 않다면 이진탐색으로 해당 원소가 알맞은 위치를 찾아 값을 대체하도록 한다.
이렇게 된다면 NlogN의 속도를 가지게 되며 다이나믹 프로그래밍을 이용한 방식보다 더 빠른 속도를 가지게 된다.