동적 계획법(DP) 최적화 기법의 이해와 적용
1. 최장 증가 부분 수열(LIS)의 로그 시간 최적화
기존 $O(N^2)$의 시간 복잡도를 갖는 최장 증가 부분 수열 문제는 세그먼트 트리나 이진 인덱스 트리(BIT), 또는 이분 탐색을 활용하여 $O(N \log N)$으로 단축할 수 있습니다. 각 단계에서 계산된 $DP[i]$ 값을 자료구조에 삽입하고, 현재 값보다 작은 원소들 중 최대 DP 값을 쿼리하는 방식으로 전이 속도를 높입니다.
...
11월 1일 20:58에 게시됨