[알고리즘] 슬라이딩 윈도우

요즘에 코딩 테스트를 풀면서 최적의 알고리즘이 무엇일지 공부하고 있다.

이번 문제를 풀면서 비교적 간단한 문제이지만 이 알고리즘 기법을 사용하면 조금 더 쉽게 문제를 풀 수 있어 공부하려고 가져와 봤다.

 

슬라이딩 윈도우란?

Sliding window는 배열이나 리스트 같은 연속된 데이터에서 특정 구간의 값을 효율적으로 계산하거나 탐색할 때 사용하는 알고리즘 기법이다.

여기서 특정 구간을 윈도우라고 지칭한다.

 

코딩 테스트 중에서 특정 구간의 합, 연속된 숫자의 조합 같은 키워드가 있을 때는 이 알고리즘을 생각하며 문제를 접근하는 것이 좋을 것 같다.

 

이 알고리즘 기법을 사용하면 전체를 매번 계산하지 않고, 이전 결과를 사용해서 반복적으로 계산을 갱신해나갈 수 있다.

function slidingWindowSum(arr, k) {
  let maxSum = 0;
  let currentSum = 0;

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

  maxSum = currentSum;

  // 윈도우를 오른쪽으로 이동
  for (let i = k; i < arr.length; i++) {
    currentSum += arr[i] - arr[i - k]; // 새로운 값을 더하고, 이전 값을 뺌
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

console.log(slidingWindowSum([1, 3, 5, 7, 9], 3)); // 출력: 21

이렇게, 코드를 보면 한 칸씩 구간(윈도우)를 이동하면서 계산을 하기 때문에 시간복잡도를 O(n) 수준으로 줄일 수 있다.

 

문제 예시를 보면서 비교해보자.

문제 예시

N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요. 만약 N=8, M=6이고 수열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

 

입력 설명

N(1≤N≤100,000), M(1≤M≤100,000,000)

 

입출력 예제

[1, 2, 1, 3, 1, 1, 1, 2] => 3

 

이 문제를 만났을 때 체크해야하는 키워드는 '연속부분수열의 합' 이 될 것이다.

 

나는 처음에 슬라이딩 윈도우 알고리즘을 몰랐기 때문에 그렇지 않은 방법으로 접근해서 풀었다.

function solution(N, M, arr) {
  let count = 0;

  for (let i = 0; i < N; i++) {
    let sum = 0;
    for (let j = i; j < N; j++) {
      sum += arr[j];

      if (sum === M) {
        count++;
        break;
      }

      if (sum > M) {
        break;
      }
    }
  }

  return count;
}

// 입력 예제
let N = 8, M = 6;
let arr = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(N, M, arr)); // 출력: 3

아마 코드 자체는 어렵지 않으리라고 생각한다.

이중 반복문을 이용해서  sum이 M과 같아졌을 때 count를 더하고, sum이 M보다 커졌을 때 이중 반복문을 벗어나서 바깥 반복문으로 되돌아가는 구조이다.

 

그렇다면 슬라이딩 윈도우를 사용하면 어떻게 작성할 수 있을까?

function solution(m, arr) {
  let start = 0;
  let end = 0;
  let currentSum = 0;
  let count = 0;

  while (end < arr.length) {
    // 윈도우 확장: end 포인터의 값을 더함
    currentSum += arr[end];

    // 현재 합이 m을 초과하면 윈도우를 축소
    while (currentSum > m && start <= end) {
      currentSum -= arr[start];
      start += 1;
    }

    // 현재 합이 정확히 m이라면 카운트를 증가
    if (currentSum === m) {
      count += 1;
    }

    // end 포인터를 이동하여 윈도우를 확장
    end += 1;
  }

  return count;
}

let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));

이 문제에서 사용되는 변수들의 값이 바뀌는 것을 풀어서 설명하면 아래와 같다.

 

순회과정

첫 번째 : end = 0

1. currentSum += nums[0] → currentSum = 1

2. 현재 합 1 < M → 윈도우 확장 (start는 그대로)

3. end 증가 → end = 1

 

두 번째 : end = 1

1. currentSum += nums[1] → currentSum = 3

2. 현재 합 3 < M → 윈도우 확장 (start는 그대로)

3. end 증가 → end = 2

 

세 번째 : end = 2

1. currentSum += nums[2] → currentSum = 4

2. 현재 합 4 < M → 윈도우 확장 (start는 그대로)

3. end 증가 → end = 3

 

네 번째 : end = 3

1. currentSum += nums[3] → currentSum = 7

2. 현재 합 7 > M → currentSum -= nums[0] → currentSum = 6  (윈도우 축소, start = 1)

3. 현재 합 currentSum === M → count++ → count = 1

4. end 증가 → end = 4

 

다섯 번째 : end = 4

1. currentSum += nums[4] → currentSum = 7

2. 현재 합 7 > M → currentSum -= nums[1] → currentSum = 5 (윈도우 축소, start = 2)

3. end 증가 → end = 5

 

여섯 번째: end = 5

1. currentSum += nums[5] → currentSum = 6

2. 현재 합 currentSum === M → count++ → count = 2

3. end 증가 → end = 6

 

일곱 번째 : end = 6

1. currentSum += nums[6] → currentSum = 7

2. 현재 합 7 > M → currentSum -= nums[2] → currentSum = 6 (윈도우 축소, start = 3)

3. 현재 합 currentSum === M → count++ → count = 3

4. end 증가 → end = 7

 

여덟 번째: end = 7

1. currentSum += nums[7] → currentSum = 8

2. 현재 합 8 > M → currentSum -= nums[3] → currentSum = 5 (윈도우 축소, start = 4)

3. end 증가 → end = 8 (반복 종료)

 

최종 상태

start = 4, end = 8, currentSum = 5, count = 3

 

이렇게 순회과정을 따라가면 어떤 범위를 확인하고 범위를 좁혀가는지 알 수 있을 것이다.

나도 처음에 알고리즘 봤을 때는 잘 이해가 가지 않았지만, 순회할 때 로그를 찍어보면서 과정을 따라가보니 확 이해가 됐다.

 

한 번의 반복만으로도 연속부분수열을 찾을 수 있다는 점에서 정말 효율적인 알고리즘인 것 같다.

 

그럼 오늘은 이만 !

안뇽 ~!