모각코 5회차 : 슬라이딩 윈도우 [Sliding Window]

슬라이딩 윈도우 [Sliding Window]

"고정된 사이즈의 윈도우를 이동시켜서 윈도우 내에 있는 데이터를 이용해

문제를 푸는 알고리즘 기법이다."

구간 합 구하기, 특정 조건을 만족하는 구간 찾기 등 

배열이나 리스트 요소의 일정 범위의 값을 비교할 때 유용하다.

 

위의 사진에서 고정된 사이즈는 3이다.

Sliding Window 알고리즘을 구현하기 위해서는 일단 초기값을 저장해야 하기 때문에

사진에서 보이는 A 부터 C 까지를 초기값으로 잡아놓는다.

이후, 각 Step마다 맨 앞의 요소를 제거 후, 맨 뒤 + 1의 Index를 추가한다.

이 동작을 반복하는 것이 Sliding Window 알고리즘의 핵심이다.

 

예시 1 : 2559 : 수열

 

코드

#include <stdio.h>

int main() {
    int n, k, sum, max;
    scanf("%d %d", &n, &k);
    sum = 0;

    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }
    max = sum;

    for (int i = k; i < n; i++) {
        sum = sum - arr[i-k] + arr[i];
        if (sum > max) max = sum;
    }

    printf("%d", max);

    return 0;
}

//
// Created by Leehyuntae on 2025-07-28.
//