TIL. 슬라이딩 윈도우 알고리즘 문제풀이

슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우 알고리즘은 연속적인 데이터의 범위에 대해 연산을 수행할 때 사용되는 기법이다. 이 방법은 주로 배열이나 리스트와 같은 선형 구조에서 효율적으로 문제를 해결하는 데 사용된다. 슬라이딩 윈도우 알고리즘의 핵심은 고정된 크기의 윈도우를 사용하여 배열을 순회하면서 윈도우 내의 데이터에 대한 연산을 수행하는 것이다.

슬라이딩 윈도우 알고리즘의 특징

1. 고정된 크기의 윈도우
윈도우 크기는 문제에 따라 고정되거나 변할 수 있다.

2. 윈도우의 이동
윈도우는 배열을 순회하면서 한 칸씩(또는 여러 칸씩) 이동한다.

3. 효율적인 연산
윈도우가 이동할 때마다 전체를 다시 계산하는 대신, 이전 상태에서의 작은 변경을 이용해 빠르게 결과를 갱신한다.

예시)
최대/최소 합 구하기: 배열에서 연속된 k개 요소의 최대 또는 최소 합을 찾는 경우
문자열 처리: 문자열에서 특정 조건을 만족하는 최소 길이의 부분 문자열 찾기

예제 : 최대합 구하기

문제) 주어진 배열에서 연속적인 K개의 요소의 합이 최대가 되는 값을 찾아라.

→ 배열 arr = [1, 3, 5, 2, 8, 1, 5] 과 K = 3이 주어진 경우, 연속된 3개 요소의 최대 합을 찾는다.

function maxSum(arr, k) {
    let n = arr.length;
    if (n < k) {
        return -1;  // 배열 크기가 k보다 작은 경우
    }

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

    let maxSum = windowSum;

    // 윈도우를 오른쪽으로 이동하면서 합 갱신
    for (let i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

// 예제 실행
const arr = [1, 3, 5, 2, 8, 1, 5];
const k = 3;
console.log(maxSum(arr, k));  // 출력: 15 (5 + 2 + 8)

🍏 풀이Tip
처음에는 배열의 첫 3개 요소의 합을 계산한다.
그 후, 윈도우를 한 칸씩 오른쪽으로 이동하면서 새로 들어오는 요소를 더하고, 왼쪽 끝의 요소를 빼서 합을 갱신한다.
이렇게 합을 갱신하면서 최대값을 찾는다.

최대 매출

문제 설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면 12 15 11 20 25 10 20 19 13 15 연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

▣ 입력설명
첫 줄에 N(5<=N<=100,000)과 M(2<=K<=N)가 주어집니다. 두 번째 줄에 N개의 첫 줄에 최대 매출액을 출력합니다.숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

▣ 출력설명
첫 줄에 최대 매출액을 출력합니다.

▣ 입출력 예

input	output
10 3 12 15 11 20 25 10 20 19 13 15	56

풀이

const maximumSales = (k, a) => {
  let maxTotal = 0;
  let total = 0;
  let i = 0;

  // 초기 윈도우의 합 계산
  while (i < k) {
    total += a[i];
    i++;
  }

  // 최초 윈도우의 매출액으로 maxTotal을 초기화
  maxTotal = total;

  // 윈도우를 이동하면서 최대 매출액 갱신
  for (i = k; i < a.length; i++) {
    total += a[i] - a[i - k];
    maxTotal = Math.max(total, maxTotal);
  }

  return maxTotal;
};

let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(maximumSales(3, a));

👉 슬라이딩윈도우 알고리즘을 적용해 보았다.

• 초기에 k 크기의 윈도우로 첫 번째 k 일 동안의 매출액의 합을 계산한다.
• 이 초기 합을 maxTotal에 할당하여, 최대 매출액을 초기화 한다.
• 그 후, 윈도우를 오른쪽으로 이동시키면서 매 단계에서 새로운 요소를 더하고, 윈도우의 가장 왼쪽 요소를 빼서 합을 갱신한다.
• 각 단계에서의 총 매출액과 현재까지의 최대 매출액을 비교해서 maxTotal 을 업데이트 해준다.
• 최종 maxTotal 을 반환한다! 😀

✍️ 가장 첫 k윈도우 를 만드는 것까지는 쉬웠지만 윈도우를 이동시키는 것에서 고민을 많이 했던 것 같다.
i를 k로 할당하는 것, a[i] 를 통해 윈도우 오른쪽으로 한칸 더하고, 특히 a[i - k] 를 통해서 윈도우의 왼쪽을 한칸 빼내는 것이 헷갈렸던 것 같다.😂

정말 이름처럼 정말 윈도우가 슬라이딩 하는 방식의 슬라이딩 윈도우 알고리즘이다!

✍️ solution

function solution(k, arr) {
  let answer,
    sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];
  answer = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    answer = Math.max(answer, sum);
  }
  return answer;
}

let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
console.log(solution(3, a));