Slidingwindow_with_deque
title: 2025-09-15 author: 강병호 date: 2025-09-15 category: TIL/강병호/2025/09 layout: post (자유) —
슬라이딩 윈도우
배열이나 리스트 같은 순차적인 데이터 구조에서 연속적인 부분 구간(윈도우)를 효율적으로 탐색하는 알고리즘 기법
투 포인터로 구현하는 기본적인 아이디어는 다음과 같다.
- 두 개의 포인터 (start, end)를 사용해 윈도우 범위 지정
- end 포인터를 오른쪽으로 이동시키며 윈도우 확장
- 특정 조건이 만족되지 않는 경우,
start포인터를 사용하여 윈도우 축소
해당 방식은 모든 부분 배열을 탐색하는 O(N^2)방식보다 효율적으로 O(N) 의 시간 복잡도를 지닌다.
윈도우의 최솟값, 최대값 처리 방식
해당 방식에 대해서 세워라 반석 위에의 문제에서 기존의 방식으로 최대, 최소를 구분하다 보니 시간 초과가 발생했다.
while (end != N) {
if (arr[end] < arr[minIndex]) {
minIndex = end;
} else if (arr[end] > arr[maxIndex]) {
maxIndex = end;
}
if (Math.abs(arr[minIndex] - arr[maxIndex]) > 2) {
result = Math.max(result, end-start);
if (maxIndex > minIndex) {
start = minIndex+1;
minIndex = start;
for (int j = start; j <= end; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
} else {
start = maxIndex+1;
maxIndex = start;
for (int j = start; j <= end; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
}
}
end++;
}
위의 min, max Index를 찾는 과정은 윈도우의 최소, 최대값을 찾는 과정에서 윈도우 내부를 for문을 사용하여 찾기에 시간복잡도가 다시 O(N^2)가 되게 된다.
이러한 시간복잡도 문제를 해결하기 위해서는 O(1)으로도 최솟값/최댓값을 파악할 수 있는 자료구조인 Deque를 사용한다.
덱을 최솟값/최댓값 후보들의 대기열로 다음과 같이 사용한다.
minDeque: 현재 윈도우에서 최솟값이 될 가능성이 있는 원소들의 인덱스를 오름차순으로 저장하여minDeque의 맨 앞에는 항상 현재 윈도우의 최솟값 인덱스가 위치하도록 한다.maxDeque: 현재 윈도우에서 최댓값이 될 가능성이 있는 원소들의 인덱스를 낼미차순으로 저장하여maxDeque의 맨 앞에는 항상 현재 윈도우의 최댓값 인덱스가 위치하도록 한다.
이를 이용하여 O(N^2)의 시간복잡도를 O(N)으로 줄일 수 있다.
우선순위 큐를 사용한다면?
해당 방식이 궁금하여 Gemini의 힘을 빌렸따.
해당 문제에 우선순위 큐를 적용하면 다음 흐름으로 이어진다.
- 윈도우 확장 (
end이동) : 새로운 원소arr[end]를 우선순위 큐에 넣는다. - 최솟값/최댓값 확인 : 큐의 맨 앞 원소를 확인하여 최솟값 또는 최댓값을 가져온다.
- 윈도우 축소 (
start이동) : 윈도우에서 빠져나가는 원소arr[start]를 우선순위 큐에서 제거해야한다.
해당 방식의 3번에서는 결국 윈도우 축소를 위해 arr[start] 를 찾아서 제거하기에 O(K) 심하면 O(N)의 시간이 걸리기 때문에 다시 시간 초과의 문제점을 가질 수 있따.
결론은 다음과 같다.
우선순위 큐: 계속해서 원소가 추가되고 가장 작은/큰 원소만 빼내는 상황에 최적화되어 있따. (예: 다익스트라 알고리즘, 가장 비용이 적은 경로 찾기)
덱 (Deque): 슬라이딩 윈도우처럼 정해진 구간 내에서 오래된 데이터를 버리고 새로운 데이터를 추가하며 최솟값/최댓값을 찾아야 하는 상황에 최적화되어 있다.