[Algorithm] 슬라이딩 윈도우(Sliding Window) 완.전.정.복

슬라이딩 윈도우(Sliding Window)란?

 슬라이딩 윈도우란, 2개의 양 끝점을 가지고, 각 끝점의 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘 입니다.

예를 들어, 설명해드리겠습니다. 1 ~ 7 까지의 배열에서 4개의 연속된 숫자의 합을 계산하는 문제입니다.

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

이처럼 고정된 크기의 범위를 유지한 채 문제를 해결하는 모습을 볼 수 있습니다.

start point(시작점)과 end point(끝점)이 함께 움직이는 모습이 특징입니다!

슬라이딩 윈도우 vs 투 포인터

 투 포인터(two pointer)과 유사한 점이 많은 알고리즘인데, 두 알고리즘 모두 시작점과 끝점이 있고(+ 양 점을 서로 갱신함), 이 범위를 유지한 채 문제를 해결하여 시간복잡도를 줄이게 해주는 점이 유사합니다! 

하지만 매우 핵심적인 차이가 존재합니다. 바로 슬라이딩 윈도우는 고정된 범위이지만, 투 포인터는 유동적인 범위라는 점입니다!

 

필자가 느끼는 둘의 차이점으로,

보통 슬라이딩 윈도우는 서로 같은 방향으로 이동 ex) 고정된 배열 start++이면 end++

투 포인터는 서로 다른 방향으로 이동 ex) 유동적인 배열 start++이면, end-- / start--이면, end++

 

이 둘의 차이점을 인지한다면, 문제를 직면했을 때 어떤 알고리즘을 써야할지의 접근을 더 빠르게 할 수 있을 것입니다!

슬라이딩 윈도우 예시 문제

21921번: 블로그

위 내용을 숙지한다면, 매우매우 쉽게 풀 수 있는 문제입니다. 현재 필자는 아래처럼 코드를 작성했지만 충분히 이보다 간결하고 쉽게 풀 수 있으리라 생각합니다. 제 코드는 절대 참고하시고, 여러분의 풀이로 문제를 해결해보세요!

(문제 해결과정은 아래 주석 참고)

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, X;
    int point = 0, max = 0, cnt = 1;
    // point = 현재 윈도우의 합
    // max = 현재 최댓값
    // cnt = 최댓값과 같은 윈도우의 수
    
	cin >> N >> X;
	vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
		if (i < X) { // index = 0 ~ X-1 까지의 합을 구한다(첫 윈도우)
			point += vec[i];
		}
	}
	max = point; // 처음의 window가 곧 최댓값이다.
	int start = 0; // 시작점
    end = X - 1; // 끝점
    
	while (end < N - 1) {
		point -= vec[start]; //index에서 처음 시작점 제거
		start++; // start index 이동
		end++; // end index 이동
		point += vec[end]; // 새롭게 가리키는 end index의 원소 추가
        // 윈도우 이동과정
        
		if (max < point) { // 현재 max보다 point가 크다면
			max = point;
			cnt = 1;
		}
		else if (max == point) { // 현재 max와 point가 같다면
			cnt++;
		}
	}
    
	if (max == 0) {
		cout << "SAD";
		exit(0);
	}

	cout << max << '\n' << cnt;


	return 0;
}

코드 리뷰는 언제나 환영입니다!