슬라이딩 윈도우 테크닉

지은·2023년 6월 1일

Algorithm

목록 보기

29/33

슬라이딩 윈도우(Sliding Window)

: 주어진 배열에서 고정 크기의 윈도우(창문)를 이동하면서, 윈도우 내의 정보를 처리하는 알고리즘 기법

배열이나 리스트와 같이 순차적인 자료구조에서 연속적인 구간을 처리해야할 때 유용하다.
구간의 합, 최댓값 또는 최솟값, 유사도를 구하는 데 활용될 수 있다.

문제 1 - 구간 합

주어진 배열의 크기가 n이고, 윈도우의 크기가 w일 때, 모든 구간 합을 배열에 넣어 리턴하라.

창문을 한 칸 옮기면, w - 1 칸은 겹친다.

이때, 창문을 옮길 때마다 w 개를 전부 다 더하는 작업을 하지 말고, 이전에 계산한 값을 사용하는 방향으로 접근해야 한다.

풀이 과정

처음에는 윈도우를 배열의 첫 번째 원소에서 시작시킨다.
이후에는 한 칸씩 오른쪽으로 이동하면서 윈도우를 이동시킨다.
이때, 윈도우 내의 원소들의 합을 구하려면, 윈도우를 한 칸씩 이동시킬 때마다 윈도우에 새로 추가되는 원소를 더하고, 이전에 제거되는 원소를 빼주면 된다.
이렇게 함으로써 매 순간 창문 내의 정보를 유지하면서 구간 합을 효율적으로 계산할 수 있다.

만약 모든 창문 위치마다 O(W)에 합을 구하면 전체가 O(NW)의 시간복잡도를 가지게 된다.

하지만 슬라이딩 윈도우 테크닉을 사용하면, 처음 한 번의 작업에 대해서만 O(W)에 구간 합을 구할 수 있고, 이후 윈도우를 한 칸씩 밀 때마다 O(1)에 구간 합을 구할 수 있다.
따라서 전체 시간복잡도는 O(N)이 된다.

function slidingWindowSum(arr, w) {
  const result = [];
  
  let windowSum = 0;
  
  // 초기 윈도우 합 구하기
  for (let i = 0; i < w; i++) {
    windowSum += arr[i];
  }
  
  result.push(windowSum);
  
  // 윈도우 이동하며 구간합 계산
  for (let i = w; i < arr.length; i++) {
    windowSum += n[i] - n[i - w]; // 새로운 값 더하고, 이전 값 빼준다.
    result.push(windowSum);
  }
  
  return result;
}

슬라이딩 윈도우라는 걸 공부하게 만든 프로그래머스 문제..

문제 2 - 연속 부분 수열 합의 개수

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000

입출력 예

elements	result
[7,9,1,1,4]	18

길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

function solution(elements) {
    const sumSet = new Set();

    for (let w = 1; w <= elements.length; w++) { // w는 window의 크기
        let windowSum = 0;
        
        for (let j = 0; j < elements.length; j++) { // 배열 elements를 순회 (j는 창문 시작 인덱스)
            if (j === 0) {                          // 맨 처음의 창문에 대해서만 직접 합을 구한다.
                for (let k = 0; k < w; k++) {       // 창문 안에 있는 요소들을 (w개)
                    windowSum += elements[k];       // windowSum에 더해준다.
                }
            } else { // 이후 창문들은 이전에 계산한 값을 활용한다.
                windowSum -= elements[j - 1];                         // 이전 값 빼주기
                windowSum += elements[(j + w - 1) % elements.length]; // 다음 값 더해주기, 원형 수열이므로 % 이용
            }
            sumSet.add(windowSum);
        }
    }
    
    return sumSet.size;
}