11003 최솟값 찾기

일정 구간에서의 최솟값을 약 O(N) (N은 배열의 길이)에 구할 수 있는 슬라이딩 윈도우 문제

슬라이딩 윈도우 과정은 다음과 같다. 기본적으로 배열의 앞과 뒤에서 처리를 해야되어서 덱의 자료구조를 사용한다

1) 맨 앞 원소의 인덱스가 구간에서 벗어난다면 제거한다

2) 뒤에서부터 자신 보다 큰 값들은 모두 제거하고, 아닐 시 그 뒤에 원소를 넣는다

3) 이때, 맨 앞의 원소가 구간에서의 최솟값이다 

 

문제: https://www.acmicpc.net/problem/11003

깃허브주소: https://github.com/surinoel/boj/blob/master/11003.cpp