슬라이딩 윈도우 · 알고리즘 노트

개념

연속한 일정 길이 구간의 정보를 유지하면서 구간을 한 칸씩 이동하는 방법입니다. 각 구간의 합을 처음부터 다시 구하는 대신 빠진 원소를 빼고 새 원소를 더합니다.

고정 길이 구간

길이 $K$ 인 첫 구간의 합을 구합니다. 오른쪽으로 한 칸 옮기면 왼쪽 끝의 값 하나가 빠지고 오른쪽에 값 하나가 들어옵니다.

$[2,1,4,3,5]$ 에서 길이 $3$ 인 구간 합은 $7,8,12$ 입니다. 첫 합 $7$ 에서 $2$ 를 빼고 $3$ 을 더하면 다음 합 $8$ 을 얻습니다.

첫 구간과 다음 구간의 합은 각각 $2+1+4$ 와 $1+4+3$ 입니다. 가운데 $1+4$ 가 겹치므로 다시 더하는 대신 빠진 $2$ 를 빼고 들어온 $3$ 을 더할 수 있습니다. 매번 길이 $K$ 의 합을 처음부터 구하면 구간마다 $K$ 번 더하지만, 이 방법은 다음 구간으로 옮길 때 두 값만 처리합니다.

같은 길이의 모든 연속 구간을 순서대로 확인할 때 적합합니다. 길이가 서로 다른 임의의 구간 합을 여러 번 묻는다면 누적 합으로 각 구간을 바로 계산하는 방법을 사용할 수 있습니다.

복잡도

원소 수를 $N$ , 구간 길이를 $K$ 라고 합니다. 첫 구간을 계산한 뒤에는 원소 하나를 빼고 하나를 더해 갱신합니다.

연산	시간복잡도	공간복잡도
첫 구간 합 계산	$O(K)$	추가 $O(1)$
전체 구간 확인	$O(N)$	입력 $O(N)$ , 추가 $O(1)$

예제

문제

길이가 $K$ 인 연속 구간 중 합이 가장 큰 구간의 합을 구하여라.

입력

첫째 줄에 원소 수 $N$ 과 구간 길이 $K$ 가 공백을 사이에 두고 주어진다. $1\le K\le N\le1\,000$ 이다.

둘째 줄에 수열의 원소 $a_1,a_2,\ldots,a_N$ 이 공백을 사이에 두고 주어진다. $1\le a_i<10\,000$ 이다.

출력

구간 합의 최댓값을 출력한다.

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int main() {
    int n, k, i, s, ans;

    cin >> n >> k;
    v.resize(n);
    for (i = 0; i < n; ++i) {
        cin >> v[i];
    }
    s = 0;
    for (i = 0; i < k; ++i) {
        s += v[i];
    }
    ans = s;
    for (i = k; i < n; ++i) {
        s -= v[i - k];
        s += v[i];
        ans = max(ans, s);
    }
    cout << ans << '\n';
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int n, k, i, s, ans;
        int[] a;

        in = new Scanner(System.in);
        n = in.nextInt();
        k = in.nextInt();
        a = new int[n];
        for (i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        s = 0;
        for (i = 0; i < k; ++i) {
            s += a[i];
        }
        ans = s;
        for (i = k; i < n; ++i) {
            s -= a[i - k];
            s += a[i];
            ans = Math.max(ans, s);
        }
        System.out.println(ans);
    }
}

Python 3

n, k = map(int, input().split())
lst = list(map(int, input().split()))
s = sum(lst[:k])
ans = s

for i in range(k, n):
    s -= lst[i - k]
    s += lst[i]
    ans = max(ans, s)

print(ans)

2.13.1 Sliding Window

개념

고정 길이 구간

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드