monotone queue
·
PS
Introduction monotone queue 란 deque 의 상태를 증가하거나 감소하도록 유지시켜 수열의 특정 구간에서 최대 또는 최소를 찾는 기법이다. 다음의 문제를 보자. http://boj.kr/11003 우리는 길이가 L 인 연속한 모든 구간들에 대해서 최솟값을 찾아줘야 한다. 물론 가장 naive한 방법으로는 세그먼트 트리를 이용한 방법이 있겠지만, monotone queue 테크닉을 사용하면 O(n)이라는 세그보다 (O(n log n)) 훨씬 빠른 속도로 문제를 풀 수 있다. 최솟값을 구하는 경우 i와 j는 i ar..
