슬라이딩 윈도우??

슬라이딩 윈도우 알고리즘은 이름에서도 알 수 있듯이, '슬라이딩'하면서 '윈도우' 범위 내의 값들을 연산하는 방식의 알고리즘이다. 여기서 '슬라이딩'은 이동하는 것을, '윈도우'는 특정 범위를 의미한다.

어떤 상황에 쓰면 좋을까?

이 알고리즘의 장점은 무엇일까? 바로 시간 복잡도와 공간 복잡도를 낮출 수 있다는 점이다.
만약 이런 알고리즘을 사용하지 않고 모든 경우의 수를 다 계산한다면, 시간 복잡도는 O(N^2)가 될 것이다.
하지만 슬라이딩 윈도우 알고리즘을 사용하면, 시간 복잡도는 O(N)으로 줄일 수 있다.

그렇기 때문에 이 알고리즘은 주어진 범위 내에서 최대값, 최소값, 합 등을 빠르게 계산할 때 유용하게 사용된다.

이제 간단한 예제를 통해 어떻게 동작하는지 살펴보도록 하자.

예를 들어, [1, 3, -1, -3, 5, 3, 6, 7]이라는 배열에서 윈도우 크기 3의 최대값을 찾는 문제가 있다고 가정하자. 슬라이딩 윈도우 알고리즘을 사용하면, 첫 윈도우 범위는 [1, 3, -1]이 될 것이고, 이 범위의 최대값은 3이다. 그 다음으로 윈도우를 한 칸씩 오른쪽으로 이동하면서 최대값을 찾아나가면 된다.

let arr = [1, 3, -1, -3, 5, 3, 6, 7];
let k = 3;  // 윈도우 크기
let result = [];

for(let i = 0; i < arr.length - k + 1; i++) {
  let max = Math.max(...arr.slice(i, i + k));
  result.push(max);
}

console.log(result);  // [3, 3, 5, 5, 6, 7]

위 코드를 보면, 윈도우 범위를 슬라이딩하면서 최대값을 계산하는 방식을 확인할 수 있다. 이렇게 슬라이딩 윈도우 알고리즘을 이용하면, 배열이나 리스트의 연속적인 부분을 효율적으로 처리할 수 있다.

이러한 알고리즘을 푸는 문제를 살펴보면
2559번 수열 문제 : https://www.acmicpc.net/problem/2559 가 있다.

해당 문제는 위 슬라이딩 윈도우 알고리즘을 이용하여 첫 K개의 합을 구하고, 그 다음부터는 이전 K개의 합에서 가장 앞의 수를 빼고 현재 수를 더하는 방식으로 K개의 연속된 수의 합을 구할 수 있다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './example.txt'; 
const input = fs.readFileSync(filePath).toString().trim().split('\n');

function solve() {
    const [N, K] = input[0].split(" ").map(Number)
    const list = input[1].split(" ").map(Number);
    let sum = 0;
    for(let i = 0 ; i< K ; i++){
        sum += list[i]
    }
    let answer = sum;
    for(let j = 1 ; j<= N-K ; j++){
        sum = sum-list[j-1]+list[j+K-1];
        answer = Math.max(sum, answer);
    }
    return answer
}

console.log(solve());

위 풀이는 슬라이딩 윈도우를 이용해서 푼 풀이이다.

같이 언급되는 알고리즘으로는 투 포인터 알고리즘이 있으며 시간이 된다면 다음에 블로깅해보겠습니다
틀린 내용이 있다면 피드백 부탁드립니다. 🙇‍♂️