핵심 코드
from bisect import bisect_left k = bisect_left(stack, lst[i]) stack[k] = lst[i]
bisect_left(stack, lst[i])
stack lst[i]보다 작은 값 중 가장 큰 값의 인덱스 반환
import sys
from bisect import bisect_left
n = int(input())
lst = list(map(int, input().split()))
stack = [0]
for i in range(len(lst)):
# 스택의 가장 큰 수가 비교하는 수보다 작으면 리스트에 추가
if stack[-1] < lst[i]:
stack.append(lst[i])
# 아니라면 현재 정렬된 stack의 원소중에서 lst[i]가 들어갈 곳의 인덱스 반환
else:
k = bisect_left(stack, lst[i])
stack[k] = lst[i]
print(len(stack[1:]))
이 문제는 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이기 때문에 답이 맞지만 실제로 나오는 답은 가장 긴 증가하는 부분 수열과는 다르다 .
그래서 실제로 증가하는 부분 수열의 원소까지 모두 구하려면 memorization 이 필요하다.