[Algorithm] LIS(Longest Increase Sequence)

LIS(Longest Increase Sequence)란?

• LIS 알고리즘은, 주어진 수열에서 숫자를 제외시켜 최장 길이의 오름차순 수열을 만드는 알고리즘이다.

---

LIS 구현

1. 이중 반복문을 통한 구현 (O(N^2))

• 해당 구간까지의 '최장 증가 부분수열'의 크기를 저장하는 별도의 list를 생성하고 이를 업데이트한다.
• array의 모든 값에 대해, 해당 값 이전까지(0 ~ i-1) 자신보다 큰 값들의(array[j] > array[i]) 개수를 dp[i]에 저장한다.
• 모든 과정이 끝나면, dp의 가장 큰 값이 array에서 만들 수 있는 '최장 증가 부분수열'의 크기 이다.

array = [3,4,1,2,6,4,3,1]
dp = [1] * len(array)

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

---

2. binary search를 통한 구현 (O(NlogN))

• 오름차순의 수열에 값의 적절한 위치를 찾기 위해, 이진 탐색(bisect_left)을 활용한다.
• array에서 구할 수 있는 '최장 증가 부분수열'을 담기 위한 별도의 list를 생성하고, array의 첫번째 값으로 초기화한다.
• dp의 마지막 값이 array의 현재값보다 크면 (dp[-1] > array[i]), 증가하는 값이 아니므로 dp에 맞는 위치를 찾아 삽입한다.
• dp의 마지막 값이 array의 현재값보다 작으면 (dp[-1] < array[i]), 차례로 증가하는 값이므로 dp오른쪽에 삽입한다.
• 모든 과정이 끝나면, dp는 array를 통해 만들 수 있는 '최장 증가 부분수열'이다.

from bisect import bisect_left

array = [3,4,1,2,6,4,3,1]
dp = [array[0]]

for i in range(n):
    if dp[-1] > array[i]:
        idx = bisect_left(dp, array[i])
        dp[idx] = array[i]
    elif dp[-1] < array[i]:
        dp.append(array[i])

---

주의할 점

• 문제에서 주어지는 '최장 증가 부분수열'의 조건에 따라 부등호가 달라질 수 있다.
  • 같은 값도 '증가'로 본다면, 구현에 등호가 포함되어야 한다.
  • 수열이 내림차순이 된다면(=최장 감소 부분수열) 부등호의 방향이 반대가 되어야 한다.