[백준] 11003번 C++ 슬라이딩 윈도우 알고리즘

https://www.acmicpc.net/problem/11003

위 문제는 단순히 최솟값을 출력하는 문제이지만, 브루트포스 방식으로 알고리즘을 해결할 수 없고 O(N log N) 혹은 O(N) 내로 해결해야 한다. 이때 적용 가능한 알고리즘이 슬라이딩 윈도우이다.

📌 슬라이딩 알고리즘?

배열이 주어졌을 때, 길이 k짜리 구간에서 최대 혹은 최솟값을 빠르게 유지하고 싶을 때 사용합니다.

기본 구조

1. 윈도우의 범위: 길이 k의 구간
2. deque를 사용하여 윈도우 내 최대 혹은 최솟값 후보 인덱스를 유지
3. 매번 윈도우가 한 칸씩 오른쪽으로 이동
4. 새로운 요소가 들어오면, deque의 뒤에서 자신보다 작거나 같은 값을 제거
5. deque의 앞에는 항상 최대 혹은 최솟값의 인덱스가 유지됨

이 방식을 이용하면 원소가 한번씩 들어가고 나오므로 O(N)으로 처리할 수 있습니다.

 

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

struct A
{
	int data; // 값
	int pos; // 위치
}; 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, L;
	cin >> N >> L;
	vector<int> arr(N);
	for (int i = 0; i < N; i++) cin >> arr[i];
	
	deque<A> dq;
	for (int i = 0; i < N; i++)
	{
		if (!dq.empty() && i == dq.front().pos + L) // deque에 최솟값이 (i-L+1 이하) 빠져야 하는 경우에는 제거함
			dq.pop_front();
		while (!dq.empty() && dq.back().data > arr[i]) // deque에 존재하는 최댓값이 arr에 있는 값보다 크면 빼야함
			dq.pop_back();
		dq.push_back({ arr[i], i });
		cout << dq.front().data << " "; // 매 차례에서 최솟값 출력
	}
}

 

 

 

참고 블로그 링크

https://ansohxxn.github.io/boj/11003/#-덱을-사용한-풀이