최장 증가 부분 수열(Longest Increasing Subsequence) 문제는 주어진 수열에서 정렬된 가장 긴 부분 수열을 찾는 문제이다.
예를 들어 주어진 수열이 10, 20, 10, 30, 20, 50이라고 하면
찾을 수 있는 가장 긴 증가하는 부분수열은 10, 20, 30, 50이다.
LIS의 길이를 구하기 위한 알고리즘은 두 가지가 있다.
1. 시간 복잡도가 O(n^2)인 방법
이중 반복문으로 구현되므로 O(n^2)의 시간 복잡도를 요구하는 방법이다.
크기가 len(arr)인 dp테이블을 선언한다.
각 인덱스(i)를 순회하면서 가능한 LIS의 최대 길이를 채워 넣는다.
이때 최초 인덱스 부터 i 직전 인덱스 까지 값들 중
arr 값이 arr[i] 보다 작은 값들 중, dp 값이 최대인 경우를 찾아 val에 저장한다
val 값에 1을 더하여 dp[i]에 채워 넣는다.
dp 테이블을 끝까지 채운 후 저장된 값들 중 최대 값을 찾으면 LIS의 길이를 구할 수 있다.
# LIS : O(n^2)의 시간 복잡도
# 구현 방법 : dp
import sys
n = int(input())
arr = list(map(int,sys.stdin.readline().split()))
dp = [0 for _ in range(n)]; dp[0] = 1
for i in range(n):
val = 0
# arr[j] < arr[i]인 j들 d[j]의 최댓값을 저장하는 변수
for j in range(i-1, -1, -1):
if arr[j] >= arr[i]: continue
if val < dp[j]: val = dp[j]
dp[i] = val + 1
print(max(dp))
2. 시간 복잡도가 O(nlogn)인 방법
bisect 라이브러리
정렬된 리스트에 원소를 삽입한 후에 다시 정렬할 필요 없도록 도와주는 라이브러리로 이진 탐색 알고리즘으로 구현되었기 때문에 O(logn)의 시간 복잡도를 가진다.
bisect.bisect_left(arr, x) : arr가 정렬되어 있다는 가정 하에 x값이 들어갈 가장 왼쪽 인덱스를 찾아서 반환해 준다.
bisect.bisect_right(arr, x) : arr가 정렬되어 있다는 가정 하에 x값이 들어갈 가장 오른쪽 인덱스를 찾아서 반환해 준다.
일단 빈 리스트에 arr[0]를 넣어서 선언한다 (dp = [arr[0]])
각 인덱스를 순회하면서
1. dp의 마지막 원소보다 arr[i]가 큰 경우 dp.append(arr[i]) : dp의 길이를 증가시킨다.
2. 그 외의 경우 dp 내부 원소 중 arr[i]가 들어갈 자리를 이진 탐색으로 찾아(dp는 정렬된 상태) 해당 인덱스에 값을 arr[i]로 바꾼다. (하지만 dp의 길이는 길어지지 않음)
# bisect_left로 인덱스를 찾으므로 비교 대상이 되는 값(직후 값)을 밀어내게 되므로 dp 리스트를 계속 가능한 가장 낮은 숫자로 업데이트 되게 된다.
이 방법의 핵심은
구하고자 하는 것(LIS의 길이)과 그 외의 것을 구분하는 것이다.
구하고자 하는 것은 LIS의 길이이지 LIS 자체가 아니므로,
중요한 것은 dp의 길이이고, dp에 저장된 값과 실제 LIS가 같은지 다른지는 중요하지 않다.
* LIS의 길이에 영향을 주는 요인은 LIS의 마지막 원소이다. 그러므로 다른 원소들은 바껴도 상관이 없다.
dp의 길이는 조건이 충족 되었을 때(dp 마지막 원소보다 arr[i]가 큰 경우)만 늘려 주고
* dp에 저장된 마지막 원소는, 성립하는 LIS의 마지막 원소와 같으므로, dp[-1] < arr[i]인 경우 LIS의 길이는 늘어나게 됨!
그 외의 경우에는 dp 리스트를 계속 가능한 낮은 숫자로 업데이트 하는 것이다.
단순하게 dp의 마지막 원소와 arr[i] 값을 비교만 하고, arr[i]가 dp에 들어갈 위치를 찾아 계속 업데이트해 주지 않는다면,
위와 같은 예시에서 제대로 작동하지 않게 된다.
# LIS : O(nlogn)의 시간 복잡도
# 구현 방법 : 이진 탐색 (bisect 라이브러리), dp
import sys
from bisect import bisect_left
n = int(input())
arr = list(map(int,sys.stdin.readline().split()))
dp = [arr[0]]
for i in range(1, len(arr)):
if arr[i] > dp[-1]: dp.append(arr[i])
else:
idx = bisect_left(dp, arr[i])
dp[idx] = arr[i]
print(len(dp))
# 중요한 것은 dp의 길이이고, dp에 현재 저장된 값과 실제 LIS가 같은지 다른지는 중요하지 않다