슬라이딩 윈도우

슬라이딩 윈도우(Sliding Window) 알고리즘은 어떤 특정 조건을 만족하는 연속 구간을 구할 때 O(N) 으로 해결할 수 있도록 도와주는 알고리즘이다.

투 포인터 알고리즘과 개념이 유사하나 구간의 길이를 고정적으로 잡기 때문에 포인터가 2개일 필요가 없다. 포인터를 하나만 알고 있어도 고정적인 길이를 알고 있기 때문에 끝이 어디인지 알 수 있다.

구간의 고정길이를 L 이라고 하면, 윈도우를 한칸 옮기더라도 옮기기 전 윈도우 안에 있던 L - 1 칸은 겹치게 된다.

• 기존 모습 : 🟨🟪🟪🟪🟪🟨🟨
• 다음 모습 : 🟨🟨🟪🟪🟪🟪🟨

기존 구간과 새 구간의 🟨🟪🟥🟥🟥🟪🟨 빨간 부분은 겹치게 된다. 따라서 새 구간에서는 빠지게 되는 앞의 🟪와 새 구간에 포함되게 된 🟪만 비교하면 더 효율적이다.

예시

구간의 최대값 구하기

N 개의 숫자가 주어질 때 연속 된 K 개의 수의 합의 최대값을 구하라.

#include <iostream>
#include <numeric>
#include <vector>

int main()
{
	int N = 10, K = 3;
	std::vector<int> Num = { 1, 5, 4, 7, 2, 10, 1 ,7, 9, 6 };

	int Sum = std::accumulate(Num.begin(), Num.begin() + K, 0); // 0 ~ K - 1 합
	int Max = Sum; // 최대값
	for (int i = K; i < N; i++)
	{
		Sum = Sum + Num[i] - Num[i - K];
		Max < Sum ? Max = Sum : Max;
	}

	std::cout << "최대값 : " << Max;
	return 0;
}

최대값 : 22