Monotone Queue Optimization

동적계획법 최적화 전략이다.

이런게 있는줄도 몰랐다는게 좀 충격이다.

좀더 생각해봤으면 영감이 떠올랐을텐데,, 문제를 풀때 떠올리지 못했던게 너무 아쉽다.

 

Deque를 이용하여 최적화 하는 전략이다.

O(N^2)의 시간복잡도를 가지를 로직을 O(N)~O(NlongN)으로 줄일 수 있다.