Monotone Queue (2) 썸네일형 리스트형 백준 15678 - 연세워터파크 www.acmicpc.net/problem/15678 단조 큐를 이용해 최적해를 빠른 속도로 계산할 수 있는 동적계획법 문제이다. 동적계획법에 단조 큐를 활용하는 과정은 다음과 같다. 1. 먼저 덱에서 현재 징검다리로 건너올 수 없는 징검다리를 모두 제거한다. 2. 지역 최적해를 가진 이전 징검다리에서 현재 징검다리로 건너올 경우의 최적해를 계산한다. 현재 징검다리를 시작점으로 해서 가지는 점수나 이전 징검다리에서 가지고 있는 최적해 + 현재 징검다리를 밟았을 때 점수 둘 중 하나가 될 것이다. 3. 계산한 최적해와 최대 점수를 비교해서 저장한다. #덱에는 이동할 수 있는 범위의 징검다리만 있으므로 계산한 최적해는 최댓값이 아닌 극댓값이라는 사실에 유의한다. 4. 현재 계산한 최적해보다 작은 값을 가지고.. 단조 큐 (Monotone Queue) 개요 큐에 들어있는 어떠한 값들의 집합이 단조성을 보이면(monotonic) 그 큐는 단조 큐가 된다. 예를 들어 큐 안에 있는 수들을 수열로 봤을 때 단조증가한다면 단조 큐다. 용어는 단조 큐이지만 이를 활용하기 위해서 덱(deque)이 쓰인다. 단조 큐를 활용한 문제 풀기 백준 저지에서 11003번 문제를 보자. 수열을 순회하면서 특정 구간에 대해 최솟값을 찾을 것을 요구하고 있다. 어떤 구간에서 최솟값보다 큰 수들은 무시된다는 점에 주목해보자. 수열을 순회하면서 상대적으로 큰 수들을 적절히 배제하고 구간에 알맞은 최솟값을 남길 수 있다면 좋을 것이다. 여기서 단조 큐를 이용하면 $O(N)$으로 빠르게 답을 구할 수 있게 된다. 11003번 문제를 푸는 과정을 통해 단조 큐 사용법을 알아보자. 1. .. 이전 1 다음
