문제 개요
n개의 원소를 가진 배열과 값 k가 주어졌다고 가정해 보겠습니다. 이때 우리가 해야 할 일은 크기가 k인 각 연속 부분 배열(슬라이딩 윈도우)에 대해 최댓값을 찾는 것입니다.
예를 들어 입력이 arr = [3,4,6,2,8]이고 k = 3이라면, 크기 3의 연속 부분 배열은 [3,4,6], [4,6,2], [6,2,8] 세 가지입니다. 따라서 각 부분 배열의 최댓값은 순서대로 6, 6, 8이 됩니다.
알고리즘 접근 방식
이 문제는 덱(deque, 양방향 큐) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 덱에는 배열 원소의 인덱스를 저장하며, 덱의 맨 앞에는 항상 현재 윈도우 내 최댓값의 인덱스가 위치하도록 유지합니다. 이 방식은 각 원소가 최대 한 번 삽입되고 한 번 제거되므로 전체 시간 복잡도가 O(n)으로 매우 효율적입니다.
해결 단계는 다음과 같습니다.
- 덱 Qi를 정의합니다.
- i := 0부터 i < k까지 반복하면서:
- Qi가 비어 있지 않고 arr[i] >= arr[Qi의 마지막 원소]인 동안 Qi의 마지막 원소를 삭제합니다.
- i를 Qi의 뒤쪽에 삽입합니다.
- i < 배열의 크기인 동안 반복하면서:
- arr[Qi의 첫 번째 원소]를 출력합니다. (현재 윈도우의 최댓값)
- Qi가 비어 있지 않고 Qi의 첫 번째 원소 <= i - k인 동안 앞쪽 원소를 삭제합니다. (윈도우를 벗어난 인덱스 제거)
- Qi가 비어 있지 않고 arr[i] >= arr[Qi의 마지막 원소]인 동안 뒤쪽 원소를 삭제합니다.
- i를 Qi의 뒤쪽에 삽입합니다.
- 마지막으로 arr[Qi의 첫 번째 원소]를 출력하여 마무리합니다.
예제 코드
아래 구현 예시를 통해 더 잘 이해해 보겠습니다.
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(){
vector<int> arr = {3,4,6,2,8};
int k = 3;
deque<int> Qi(k);
int i;
for (i = 0; i < k; ++i){
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
Qi.push_back(i);
}
for ( ; i < arr.size(); ++i){
cout << arr[Qi.front()] << " ";
while ( (!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front();
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
Qi.push_back(i);
}
cout << arr[Qi.front()] << endl;
}입력
{3,4,6,2,8}, 3출력
6 6 8
정리
단순히 각 윈도우마다 최댓값을 일일이 계산하면 O(n×k)의 시간이 걸리지만, 덱을 활용한 위 알고리즘은 O(n)으로 최적화할 수 있습니다. 슬라이딩 윈도우 최댓값 문제는 코딩 테스트와 실전 시스템(예: 스트리밍 데이터 처리)에서 자주 등장하는 유형이므로, 덱 기반 풀이법을 꼭 익혀두시기 바랍니다.