알고리즘

백준 1045번 '도로' 문제를 살펴보자. Union-Find와 입력 순서의 특성을 그리디하게 이용하면 O(N^2)의 알고리즘을 작성할 수 있다.

Parametric Search를 적용할 수 있는 전형적인 최적화 문제이다. Parametric Search와 큐를 이용해 O(NlogN)의 알고리즘을 작성해보자.

일반적인 배낭 문제인 듯 하지만 생각해볼 요소가 추가되었다. 문제의 특수한 입력값을 잘 정제하여 O(NM)의 배낭 알고리즘을 구현해보자.

입력값을 적절히 처리하여 O(NlogN) LIS 문제로 바꿔 풀어본다.