코딩스토리

www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 덱과 슬라이딩 윈도우 알고리즘을 사용하면 되는 문제였다. 해결방법은 다음과 같다. 하나의 덱에 최솟값에 대한 정보를 담고 있는다. 이때 이 덱의 크기는 최대 L까지 이다. 그리고 이 덱에는 최솟값들의 후보를 모두 가지고 있는다. 또한 이 덱은 오름차순 정렬이 되어 있다. 무슨 소리인가 할 수 있는데 천천히 살펴보면 생각보다 어렵지 않게 구현이 가능하다. 먼저 덱에 최솟값에 대한 ..