가장 긴 증가하는 부분 수열(LIS) 풀기

입력값 개수에 따라 다른 전략을 취할 수 있다

1. DP

문제: https://www.acmicpc.net/problem/11053

n = int(input())
arr = list(map(int, input().split()))

dp = [1] * n # i번째 인덱스까지 최장 길이를 담고 있는 dp 배열
for i in range(n):
   for j in range(i):
       if arr[i] > arr[j]:
           dp[i] = max(dp[i], dp[j] + 1)
           
print(max(dp))

시간복잡도: O(n^2)

가장 기본적인 접근 방식은 DP를 활용하는 것이다. 이전 값들과 비교해가며 갱신하는 방식이므로, O(n^2)의 시간복잡도를 가진다.

2. 이분탐색 활용 : bisect

문제: https://www.acmicpc.net/problem/12015

import sys
from bisect import bisect_left

n = int(input())
arr = list(map(int, sys.stdin.readline().split()))

lst = [0]

for a in arr:
    if lst[-1] < a:
        lst.append(a)
    else:
        lst[bisect_left(lst, a)] = a

print(len(lst) - 1)

시간복잡도: O(n log n)

처음에 이 아이디어가 이해 안 갔는데, lst에는 실제 최장 길이 수열이 들어가지 않기에, lst의 내용에 집중하면 안되고 문제에서 요구하는 길이를 구할 수 있다는 사실을 알아야 한다.

기본적인 아이디어는, 전체 배열을 돌면서 lst에 들어갈 적절한 위치를 구해서 그 위치에 원소를 대체하는 방식이다.

가장 긴 길이의 부분 수열을 구할 수 있다는 건 보장할 수 있는 이유는 무엇일까? 그건 lst의 길이가 길어지는 시점은 가장 최근 원소가 제일 클 때이기 때문이다. (lst[-1] < a 일 때)

그렇지 않은 경우에는 적절한 위치의 원소를 대체하기 때문에, 길이가 유지된다. 다만, lst의 내용이 실제 LIS와는 다르다는 점을 알아야 한다.

참고: https://jainn.tistory.com/90