정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 풀이 인덱스 트리를 이용하여 풀어보려고도 했는데,,, 재귀로 하면 TLE가 난다. 비재귀 세그 트리를 써야 한다는데 나중에 알아봐야겠다. 도저히 모르겠어서 찾아본 결과 deque을 이용한 O(N) 풀이를 찾았다. 슬라이딩 윈도우 기법을 사용하되, 가지고 갈 필요가 없는 원소들은 바로바로 빼 줄 것이다. 0. pair를 이용하여 각 원소에 순서를..