[알고리즘 공부] 슬라이딩 윈도우 알고리즘

0. 개요

최근 백준에서 풀었던 문제가 슬라이딩 윈도우 알고리즘을 사용해서 푸는 문제였다.

문제를 풀면서 자연스럽게 어떻게 구성된 알고리즘인지는 알았지만,

더 근본적으로 공부해보면 좋겠다는 생각이 들어서 공부하게 되었다.

 

참고로 해당 문제는 회전 초밥 문제였다.

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

 

1. 알고리즘 개념

슬라이딩 윈도우는 배열이나 문자열 등의 연속된 구간을 효율적으로 탐색하는 알고리즘 기법이다.

위의 사진처럼 하나의 고정된 윈도우가 있다고 생각하고 한 칸씩 밀면서 탐색하는 알고리즘이다.

 

연속된 구간에서 특정 영역을 탐색하는 알고리즘이기에,

연속된 원소 중 최대합/최소합을 구하거나, 특정 조건을 만족하는 개수 등의 문제에서 사용될 수 있다.

위의 회전 초밥 문제 역시 특정 k개의 초밥 중 가장 다양한 개수의 초밥을 먹을 수 있는 구역을 구하는 문제이기에 해당 알고리즘을 사용했다.

 

2. 알고리즘 구조

슬라이딩 윈도우를 사용한 문제들은 보통 특정한 "규칙"을 따라야 한다.

따라서 아래에 예시는 n개의 연속된 수열에서 k개의 원소를 합쳤을 때 최대값이 되는 경우를 탐색한다고 가정하였다.

1) 초기 윈도우 상태 구성하기

int n = 10; // 수열 최대 개수
int k = 4; // 구간 크기
vector<int> arr(10); // 수열 (데이터는 이미 들어가 있다고 가정)

int sum = 0; // 합

// 초기 윈도우 (0 ~ k-1 번째 원소까지의 합) 구성
for(int i = 0; i < k; ++i)
{
	sum = arr[i];
}

2) 윈도우를 한 칸씩 이동하며 탐색

int n = 10; // 수열 최대 개수
int k = 4; // 구간 크기
vector<int> arr(10); // 수열 (데이터는 이미 들어가 있다고 가정)

int sum = 0; // 합

...

int max = sum; // 최대 합

for(int i = k; i < n; ++i
{
	sum += arr[i]; // 추가로 들어온 원소 더하기
    sum -= arr[i - k]; // 앞에서 밀려난 원소 빼기
    
    if(max < sum)
    	max = sum;
}

 

3. 알고리즘 구현

위에서 내가 구현했던 회전 초밥 문제의 코드를 첨부하겠다.

#include <stdio.h>
#include <vector>
#include <unordered_map>

using namespace std;

void FindAndPlus(unordered_map<int, int>& m, int key, int plusValue)
{
	if (m.find(key) == m.end())
	{
		m[key] = plusValue;
	}
	else
	{
		m[key] += plusValue;
	}

	if (m[key] <= 0)
	{
		m.erase(key);
	}
}

int main()
{
	int n, d, k, c;
	scanf_s("%d %d %d %d", &n, &d, &k, &c);

	vector<int> v(n);
	for (int i = 0; i < n; ++i)
	{
		scanf_s("%d", &v[i]);
	}

	if (k == n)
	{
		printf("%d", n);
		return 0;
	}

	int max = 0;
	int start = 0, end = k;
	unordered_map<int, int> m;
	m.reserve(d);
    
    // 1. 초기 윈도우 구성
	for (int i = start; i < end; ++i)
	{
		FindAndPlus(m, v[i], 1);
	}

	max = m.size() + (m.count(c) > 0 ? 0 : 1);

	// 2. 윈도우를 한 칸씩 밀면서 탐색
 	for (int i = 1; i < n; ++i)
	{
		FindAndPlus(m, v[start], -1);
		FindAndPlus(m, v[end], 1);

		end = (end + 1) % n;
		start = (start + 1) % n;

		int count = m.size() + (m.count(c) > 0 ? 0 : 1);
		if (max < count)
			max = count;
	}

	printf("%d", max);

	return 0;
}

 

4. 참고 사이트

https://coding-je.com/entry/Algorithm-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Sliding-Window-Algorithm