덱으로 슬라이딩 윈도 최댓값 구하기
O(n)에 윈도의 양 끝값을 유지합니다
덱으로 슬라이딩 윈도 최댓값 구하기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
슬라이딩 윈도우 최댓값
배열과 윈도우 크기 k가 주어졌을 때, 윈도우를 오른쪽으로 이동하면서 각 윈도우의 최댓값을 구하려고 합니다. 단순하게 구현하면 O(n 곱하기 k)입니다.
더 빠른 방법
단조 덱을 사용하면 배열을 한 번만 순회하면서 모든 윈도우의 답을 총 O(n) 시간에 구할 수 있습니다.
다시 인덱스 저장하기
값이 아니라 덱에 인덱스를 저장합니다. 인덱스를 사용하면 앞쪽 항목이 현재 윈도우 밖으로 밀려났는지 확인할 수 있습니다.
from collections import deque
dq = deque()
res = []내림차순 유지하기
덱은 앞에서 뒤로 값이 내림차순이 되도록 유지합니다. 따라서 앞쪽 인덱스는 항상 윈도우의 최댓값을 가리킵니다.
작은 뒤쪽 항목 제거하기
인덱스 i를 추가하기 전에 뒤쪽에서 값이 작은 항목을 꺼냅니다. 그런 항목은 앞으로 최댓값이 될 수 없기 때문입니다.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()새 인덱스 추가하기
뒤쪽의 가능성이 낮은 항목을 모두 제거한 뒤 현재 인덱스를 append합니다. 다음 단계에서도 덱의 순서가 올바르게 유지됩니다.
dq.append(i)오래된 앞쪽 항목 제거하기
앞쪽 인덱스가 윈도우 범위를 벗어나면 popleft합니다. 크기가 k인 윈도우는 인덱스 i에서 k를 뺀 뒤 1을 더한 위치에서 시작합니다.
if dq[0] <= i - k:
dq.popleft()각 최댓값 기록하기
인덱스 k에서 1을 뺀 위치에 첫 번째 완전한 윈도우가 만들어지면, 그 이후 모든 위치에서 덱의 앞쪽 항목이 정답을 담습니다.
if i >= k - 1:
res.append(nums[dq[0]])제거 순서에 주의하기
정답을 읽기 전에 오래된 앞쪽 항목을 제거해야 합니다. 그렇지 않으면 이미 윈도우를 벗어난 최댓값을 보고할 수 있습니다.
선형 시간이 유지되는 이유
각 인덱스는 최대 한 번 추가되고 한 번 제거됩니다. 따라서 덱 작업은 단계마다 분할 상환 O(1)이고 전체적으로 O(n)입니다.
최솟값 윈도우, 같은 아이디어
슬라이딩 윈도우의 최솟값을 구하려면 덱을 오름차순으로 유지하면 됩니다. 뒤쪽을 정리할 때 비교만 뒤집으면 됩니다.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()확인 문제
슬라이딩 윈도우 최댓값 문제에서 단조 덱의 앞쪽에는 무엇이 저장되어 있을까요?
복습: 덱으로 윈도우 해결하기
인덱스로 이루어진 내림차순 덱을 유지했습니다. 작은 뒤쪽 항목을 정리하고 오래된 앞쪽 항목을 제거한 뒤, 각 윈도우의 최댓값을 O(n)에 앞쪽에서 읽습니다. 🏆
자주 묻는 질문
“덱으로 슬라이딩 윈도 최댓값 구하기” 강의는 무료인가요?
네 — “덱으로 슬라이딩 윈도 최댓값 구하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“덱으로 슬라이딩 윈도 최댓값 구하기”에서 뭘 배우나요?
O(n)에 윈도의 양 끝값을 유지합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“덱으로 슬라이딩 윈도 최댓값 구하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 괄호 짝 맞추기를 위한 스택
- 단조 스택: 다음으로 큰 원소
- 큐와 collections.deque
- 덱으로 슬라이딩 윈도 최댓값 구하기