슬라이딩 윈도우 알고리즘

이번 포스트에서는 앞서 살펴봤던 투포인터와 아주 유사한 슬라이딩 윈도우에 대해 살펴보자.

https://soeasyalgo.tistory.com/47

투포인터

 

슬라이딩 윈도우(Sliding Window) 알고리즘

 

문제 살펴보기

먼저 Sliding Window를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자.

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

21921번: 블로그

 

기본적인 접근

주어진 기간 X 동안 블로그에 방문한 방문자를 쭉 더해주기만 하는 아주 간단한 문제이다. 

결국 이 문제는 N과 X의 크기에 따라 시간 복잡도가 결정되기 때문에 O(N*X)만에 풀수 있는 문제이다. 하지만 N과 X의 범위는 1≤X≤N≤250,000으로 대략 잡아도 600억이 훌쩍 넘어간다. 따라서 주어진 시간 내에는 풀 수가 없는 문제가 된다.

 

 

슬라이딩 윈도우의 컨셉

슬라이딩 윈도우의 핵심 컨셉도 투포인터와 마찬가지로 이미 한번 구했던 값을 버리지 않고 재사용하는데 있다.

 

슬라이딩 윈도우 알고리즘은 이름을 정말 잘 지은 알고리즘이다. 아래 그림과 같은 미닫이 형태의 슬라이딩 윈도우가 있다고 생각해보자. 우리는 언제나 고정 폭의 윈도우를 통해 창 밖을 바라본다. 

 

윈도우만 개방되어있고 나머지는 폐쇄되어있는 상태에서 창문을 오른쪽으로 살짝 밀어보면 어떤일이 발생할까? 왼쪽에 보여지는 풍경은 점점 없어질 것이고 그와 동일한 크기만큼 오른쪽에 새로운 풍경이 추가된다. 이 과정에서 중간에 보여지는 영역은 그대로 유지되는 즉 재사용 될 수 있는 영역이 된다.

 

이 개념을 그대로 배열에 적용해보자.

 

 먼저 초기 윈도우에 해당하는 영역의 값을 어렵지 않게 구할 수 있는데 이때 O(X)의 시간이 소요된다. 이후 점차 윈도우를 움직여볼텐데 맨 왼쪽 index에 해당하는 값은 하나 빼주고 오른쪽 index에 해당하는 값을 하나 더해주면 된다. 중간의 숫자들은 이미 계산된 값이 재사용된다. 이 과정에서는 두 번의 상수 시간만 소요될 것이다. 

 

따라서 전체적으로 O(N)의 시간이면 문제를 해결할 수 있게 된다.

 

중간의 계산 결과를 재사용한다는 측면에서 앞서 살펴본 Two Pointer와 매우 유사한 알고리즘인데 가장 큰 차이점은 고정폭의 윈도우를 사용한다는 점에 있다고 볼 수 있다.

package bj.silver.l3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2022. 12. 26.
 * @see https://www.acmicpc.net/problem/21921
 * @git
 * @youtube
 * @performance 37596 288
 * @category #슬라이딩윈도우
 * @note 250000*250000 =  62_500_000_000는 시간 초
 */

public class BJ_S3_21921_블로그 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;
    static int N, X;

    static int[] visitor;
    static int CNT;
    static int MAX_VISITORS;  // 250000 * 8000 = 2,000,000,000, Integer.MAX_VALUE = 2,147,483,647

    public static void main(String[] args) throws IOException {
        System.out.println(250_000L*250_000 +" : "+125000*125000L);
        input = new BufferedReader(new StringReader(instr));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        X = Integer.parseInt(tokens.nextToken());
        visitor = new int[N];
        tokens = new StringTokenizer(input.readLine());
        for (int n = 0; n < N; n++) {
            visitor[n] = Integer.parseInt(tokens.nextToken());
        }

        for (int x = 0; x < X; x++) {
            MAX_VISITORS += visitor[x];
        }
        CNT = 1;

        int base = MAX_VISITORS;
        for (int n = X; n < N; n++) {
            base -= visitor[n - X];
            base += visitor[n];
            if (base == MAX_VISITORS) {
                CNT++;
            } else if (base > MAX_VISITORS) {
                MAX_VISITORS = base;
                CNT = 1;
            }
        }
        if (MAX_VISITORS == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(MAX_VISITORS + "\n" + CNT);
        }
    }

    // REMOVE_START
    public static String instr = "5 3\n"
                                 + "0 0 0 0 0";
    // REMOVE_END

}