열렬히.뛰기

LIS 알고리즘

알고리즘: 이론 > 알고리즘 : 동적계획법 (심화) > LIS 알고리즘

LIS란?

  • Longest Increasing Subsequence, 최장 증가 부분 수열의 약자

  • 원소가 n개인 배열 중 일부로 수열을 만들 때,

    1. 각 원소가 이전 원소보다 크다는 조건을 만족하고
    2. 그 길이가 최대인 부분 수열.

  • 예를 들어 주어진 배열이 { 6, 2, 5, 1, 7, 4, 8, 3 } 인 경우.

    LIS는 { 2, 5, 7, 8 } 이 됩니다.

LIS 길이 구하기 (1)

  • LIS를 찾기 위해서는 DP를 이용한다.
  • 시간복잡도 : O(N^2)
python
## 가장 긴 증가하는 부분 수열

n = int(input())
arr = list(map(int, input().split()))
dp = list([1] * n)

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

print(max(dp))

LIS 길이 구하기 (2)

  • 이분탐색을 사용하면 LIS의 길이를 더 빠르게 구할 수 있다.
  • 시간복잡도 : O(log(N))
python
from bisect import bisect_left

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

for i in range(1, len(arr)):
    if arr[i] > x[-1]:
        x.append(arr[i])
        dp.append(dp[-1] + 1)
    else:
        idx = bisect_left(x, arr[i])
        x[idx] = arr[i]

print(dp[-1])