[Algorithm] 슬라이딩 윈도우 Sliding Window 알고리즘 톺아보기

슬라이딩 윈도우 알고리즘 개념

---

슬라이딩 윈도우 알고리즘(Sliding Window Algorithm)은 배열과 같은 선형 자료구조에서 연속된 구간 내의 데이터를 효율적으로 처리하기 위해 사용하는 기법이다. 특히 배열 내 연속된 요소의 합, 최댓값, 최솟값 등을 계산할 때 유용하다.

 

슬라이딩 윈도우는 이름 그대로 고정/가변 크기의 범위(윈도우)를 이동(슬라이드) 시키면서 필요한 계산을 반복하는 방식이다. 이때 전체 배열을 한 번만 순회하면 되기 때문에 중복 연산을 피하고 시간 복잡도를 개선할 수 있다. 일반적으로 슬라이딩 윈도우 기법을 사용하면 O(n)의 시간 복잡도로 문제를 해결할 수 있다.

// 주어진 배열에서 연속된 k개 요소의 최대 합을 찾는 함수
function maxSumSubarray(arr, k) {
  let maxSum = 0;
  let windowSum = 0;

  // 초기 윈도우(k개의 요소) 합 계산
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;

  // 슬라이딩 윈도우 이동
  for (let end = k; end < arr.length; end++) {
    const start = end - k;
    // arr[end]가 새로 추가되는 요소 이므로 arr[end] - arr[start] 순서로 계산
    windowSum += arr[end] - arr[start];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

const result = maxSumSubarray([2, 1, 5, 1, 3, 2], 3);
console.log(result); // 9

 

위 예시는 슬라이딩 윈도우 기법을 사용하여 배열 내 연속된 k개 요소의 최대 합을 찾는 함수다. 예를 들어 초기 배열 [2, 1, 5, 1, 3, 2] 에서 처음 3개 요소의 합은 2 + 1 + 5 = 8 이다. 이후 윈도우를 한 칸씩 이동하면서 k개의 요소를 더해 나간다.

 

• (215)132 → 2 + 1 + 5 = 8
• 2(151)32 → 1 + 5 + 1 = 7
• 21(513)2 → 5 + 1 + 3 = 9 (최댓값)
• 215(132) → 1 + 3 + 2 = 6

 

한편 매번 윈도우에 있는 모든 k개 요소를 반복해서 더할 필요 없이, 이전 윈도우에서 계산한 값에, 새로 추가할 요소와 제거할 요소를 반영하면 합계를 더 효율적으로 업데이트할 수 있다. 이전 윈도우 계산값 + (추가하는 요소 - 빠지는 요소)

 

시각적으로 표현해 보면 아래와 같다.

슬라이딩 윈도우 기법으로 배열내 연속된 k개 요소의 최대 합을 찾는 과정

 

슬라이딩 윈도우 알고리즘 활용

---

프로그래머스 레벨 2 - 할인행사 문제(131127)도 슬라이딩 윈도우 기법을 활용할 수 있다. 주어진 할인 목록(discount)에서 10일 연속 구간에 포함되어 있는 제품/수량과, 구매하고 싶은 제품/수량이 정확히 일치하는 경우의 총개수를 구하는 문제다.

 

• want: 구매 제품 목록 (배열)
• number: 구매 제품 수량 (배열, want 배열 인덱스와 매핑)
• discount : 할인 제품 목록 (배열, 각 인덱스는 날짜를 가리킴)

 

문제를 해결하려면 discount 배열을 0번 인덱스부터 순회하면서, 해당 위치에서 시작하는 10일 구간의 할인 제품/수량이, 구매 제품/수량과 일치하는지 여부를 확인하면 된다.

 

이때 10일 구간의 모든 제품 수량을 매번 계산할 필요 없이, 이전 구간에서 계산한 윈도우 정보에 추가/제거되는 제품의 수량만 조절하는 방식으로 불필요한 연산을 줄일 수 있다.

const WINDOW_SIZE = 10;

function solution(want, number, discount) {
  const wantMap = want.reduce((map, item, i) => map.set(item, number[i]), new Map());
  const windowMap = new Map();
  let count = 0;

  // 초기 윈도우 설정 (첫 10일)
  // chicken => 1, apple => 3, banana => 2, rice => 2, pork => 2
  for (let i = 0; i < WINDOW_SIZE; i++) {
    windowMap.set(discount[i], (windowMap.get(discount[i]) ?? 0) + 1);
  }

  // 현재 윈도우가 조건을 만족하는지 확인
  const checkIfValid = () => {
    for (const [item, qty] of wantMap.entries()) {
      if ((windowMap.get(item) ?? 0) < qty) return false;
    }
    return true;
  };

  // 첫 10일 체크
  if (checkIfValid()) count++;

  // 슬라이딩 윈도우로 탐색
  for (let i = WINDOW_SIZE; i < discount.length; i++) {
    const oldItem = discount[i - WINDOW_SIZE]; // 이전 항목 제거
    const newItem = discount[i]; // 새로 추가된 항목 추가

    // 윈도우 업데이트
    // i10 = chicken => 1, apple => 3, banana => 2, rice => 2, pork => 2
    // i11 = chicken => 0, apple => 3, banana => 2, rice => 2, pork => 2, pot => 1
    // i12 = chicken => 0, apple => 2, banana => 3, rice => 2, pork => 2, pot => 1
    // ...
    windowMap.set(oldItem, windowMap.get(oldItem) - 1);
    windowMap.set(newItem, (windowMap.get(newItem) ?? 0) + 1);

    // 조건 만족 여부 체크
    if (checkIfValid()) count++;
  }

  return count;
}

const want = ["banana", "apple", "rice", "pork", "pot"];
const number = [3, 2, 2, 2, 1];
const discount = [
  "chicken",
  "apple",
  "apple",
  "banana",
  "rice",
  "apple",
  "pork",
  "banana",
  "pork",
  "rice",
  "pot",
  "banana",
  "apple",
  "banana",
];

const result = solution(want, number, discount);
console.log(result); // 3

 

1. 구매해야 하는 제품 목록/수량을 매핑한 Map 생성 (wantMap)
2. 초기 윈도우 Map 생성 (windowMap)
3. 슬라이딩 윈도우로 discount 배열 탐색 및 windowMap 업데이트
4. 업데이트한 windowMap과 wantMap 비교

 

위 과정을 시각적으로 표현해 보면 아래와 같다.

슬라이딩 윈도우 기법으로 discount 배열을 탐색하면서 윈도우를 업데이트하는 과정

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요