슬라이딩 윈도우 최솟값 계산기
수열 위에서 고정 크기 윈도우를 옮기며 각 위치의 최솟값을 단조 덱(monotonic deque)으로 O(n)에 구하는 과정을 스텝별로 보여줍니다.
수열 (쉼표·공백으로 구분)
윈도우별 최솟값
-1, -3, -3, -3, 3, 3
스텝별 덱 상태
| i | 값 | 뒤에서 제거 | 앞에서 제거 | 덱 상태 | 윈도우 최솟값 |
| 0 | 1 | · | · | [1] | · |
| 1 | 3 | · | · | [1, 3] | · |
| 2 | -1 | 3, 1 | · | [-1] | -1 |
| 3 | -3 | -1 | · | [-3] | -3 |
| 4 | 5 | · | · | [-3, 5] | -3 |
| 5 | 3 | 5 | · | [-3, 3] | -3 |
| 6 | 6 | · | -3 | [3, 6] | 3 |
| 7 | 7 | · | · | [3, 6, 7] | 3 |
덱은 항상 값이 오름차순이 되도록 유지됩니다. 새 값보다 크거나 같은 뒤쪽 원소는 앞으로 최솟값이 될 수 없어 미리 제거되고, 윈도우를 벗어난 앞쪽 원소도 제거됩니다 — 그래서 덱의 맨 앞이 항상 현재 윈도우의 최솟값입니다.
사용 방법
- 1수열과 윈도우 크기를 입력합니다.
- 2각 위치에서 덱이 어떻게 갱신되는지(뒤에서 제거·앞에서 제거) 확인합니다.
- 3윈도우별 최솟값을 확인합니다.
자주 묻는 질문
덱(양쪽으로 넣고 뺄 수 있는 큐)에 인덱스를 저장하되, 항상 값이 오름차순이 되도록 유지합니다. 새 값을 넣기 전에 덱 뒤쪽에서 새 값보다 크거나 같은 원소를 계속 제거하고(그 원소들은 앞으로 절대 최솟값이 될 수 없으므로), 덱 앞쪽에서 윈도우를 벗어난 원소를 제거합니다. 그러면 덱의 맨 앞이 항상 현재 윈도우의 최솟값입니다.
각 원소는 덱에 많아야 한 번 들어가고 한 번 나갑니다(뒤에서 제거되거나, 앞에서 제거되거나). 그래서 전체 삽입·제거 횟수가 최대 2n번이라 전체 시간이 O(n)입니다 — 매 위치마다 윈도우를 다시 훑으면 O(nk)가 걸립니다.
단조 스택은 수열 전체에서 "다음/이전 더 큰(작은) 원소"를 찾는 문제를 풉니다. 이 도구는 "고정 크기 윈도우 안의 최솟값"을 구하는 다른 문제입니다. 둘 다 단조성(monotonicity)을 이용해 O(n)에 푼다는 점은 비슷하지만, 이 문제는 자료구조로 스택이 아니라 양쪽에서 넣고 뺄 수 있는 덱이 필요합니다.
알아두면 좋은 점
- [5,3,4], k=2 예제의 스텝별 덱 상태·제거 내역을 손으로 계산해 정확히 일치하는지 검증했습니다.
- 무작위 수열 100개에서 단조 덱 결과가 매 위치마다 윈도우를 직접 훑는 브루트포스 방식과 정확히 일치하는지 확인했습니다.
함께 보면 좋은 도구
단조 스택수열의 각 원소마다 다음 큰 원소·이전 큰 원소를 O(n)에 찾고, 같은 뼈대로 히스토그램의 최대 직사각형 넓이를 냅니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.2의 보수 변환N비트 폭에서 정수를 2의 보수 이진 표현으로 바꿔 줍니다.
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.