Sliding Window 기법 배워보기

Sliding Window 알고리즘이란?

배열 문제를 풀 때, 자주 이용되는 접근법이다. 보통 배열의 부분 배열(subarray)을 구하는 문제로 나온다.

부분 배열이란, [1, 2, 3, 4, 5] 와 같은 배열이 있을 때 [2, 3, 4] 와 같은 배열을 의미한다. [2, 4, 5] 처럼 연속되지 않으면 부분 배열이 아니다.

sliding window 풀이 방식을 이용하면, Two pointers 전략과 비슷하게 2개의 포인터를 이용한다. 보통 첫번째 포인터가 시작점 (left bound)이 되고 두번째 포인터가 끝점 (right bound)이 된다.

마치 창문을 옆으로 밀어 이동시키는 것과 비슷하여, sliding window 라고 부른다.

특정 조건을 만족하는 부분 배열 (subarray) 을 구해야 한다면, 이 접근법을 사용한다.

알고리즘 적용 순서

• left bound 와 right bound 를 정의한다. 보통은 둘다 0 번 인덱스에서 시작한다.
• right bound 를 하나씩 늘려가며 조건을 확인한다.
• 조건이 맞지 않는다면 left bound 를 조건이 맞을 때까지 right bound 와 같거나 작은 수 범위 내에서 증가시킨다.
• right bound 가 끝에 도달하면, 보통 알고리즘이 끝난다.

left bound 가 right bound 를 넘어서거나 뒤로 돌아가는 일이 없으므로, 복잡도는 O(n) 이 된다.

function fn(arr) {
  // left bound 초기화, right bound 는 for 문에서 초기화
  let left = 0;
  // right bound 끝까지 반복하기, (right bound 를 하나씩 늘린다.)
  for (let right = 0; right < arr.length; right++) {
    // 조건 맞을 때까지 left bound 더해주기
    while(left <= right && 특정 조건) {
      left++;
    }
  }
}

문제 1

양수 숫자 배열 arr 과 정수 k 가 주어졌을 때, 합이 k 보다 작거나 같은 부분 배열 (subarray) 을 구하라.

function sw(a, k) {
  // 왼쪽, 오른쪽 바운드
  let l = 0;
  let r = 0;
  // 조건을 검증하기 위한 변수
  let cur = 0;
  // 정답을 저장해놓기 위한 변수
  let ans = 0;

  while (r < a.length) {
    // 조건 검증을 위한 값 저장
    cur += a[r++];

    // 오른쪽 바운더리를 늘렸는데 현재의 숫자가 k 보다 커진다면, 왼쪽 바운더리를 늘려 합을 작게 만든다.
    while (cur > k && l <= r) cur -= a[l++];

    // 정답 기록
    ans = Math.max(ans, r - l);
  }

  return ans;
}

• 머릿속에서 한 계산 방식 을 그대로 코드로 옮겼다.
  • 휴리스틱하게 생각하면 r 을 증가시켜 시작점 0칸에서 1칸 2칸씩 오른쪽으로 차츰 늘려가면 된다.
  • 그러다가 k 보다 값이 커지는 경우, k 보다 작거나 같아질 때까지 l 을 늘려 전체 합이 작아지게 한다.
• 시간 복잡도는 위에 기재한대로 O(n) 이며, 공간 복잡도는 O(1) 이다.

위의 휴리스틱한 방식은 subarray 가 '순서가 있고', '연속된 배열' 이라는 가정 하에 유추해낼 수 있다.

모범 답안

var findLength = function (nums, k) {
  let left = 0,
    curr = 0,
    ans = 0;
  for (let right = 0; right < nums.length; right++) {
    curr += nums[right];
    while (curr > k) {
      curr -= nums[left];
      left++;
    }

    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};

• 내가 작성한 코드와 r 이 증가하는 타이밍이 다르기 때문에 마지막 ans 를 구할 때 +1 을 해주어야 한다.

약간의 개인적인 피드백

• 처음 한 생각에서 코드를 고칠 때 변화하는 부분을 잘못 생각해서 코드 고치다가 조금 헤맸다.
  • 연산 방식을 고치면서 ans 를 구하는 부분까지 영향을 받을 것이라 생각을 못함.
  • 내가 이 코드를 고치면 어느 부분까지 영향을 미칠지 생각해야 한다.

문제 2

0 과 1 로 구성된 이진수 문자열 s 를 받았을 때, 1 로만 이루어진 가장 긴 배열의 길이를 구하라. 단, 딱 한번 0 과 1 을 뒤집을 수 있다.

s 가 "1101100111" 일 때, 답은 5이다. 1111100111 와 같이 한번 뒤집을 수 있기 때문이다.

처음 생각한 아이디어

• 0을 만난 위치를 기록한다.
• 처음에는 -1 을 기록한다.
• 두번째 0 을 만났을 때 left bound 를 전전에 만난 0 의 위치로 이동한다.
• ans 에는 r - 전전에 만난 0 의 위치 를 기록한다.

/**
 * @param s binary string ex) 01100111
 */
function sw2(s) {
  let ans = 0;
  let zeros = [];
  let r = 0;

  while (r < s.length) {
    if (s[r] === "0") {
      zeros.push(r);
    }

    const lastZero = zeros.length > 1 ? zeros[zeros.length - 2] : -1;

    ans = Math.max(ans, r - lastZero);
    r++;
  }

  return ans;
}

힌트를 보고 생각한 아이디어

• 0 의 개수를 curr 라는 변수에 담아둔다.
• r 을 1 씩 증가시키며 윈도우의 사이즈를 증가시킨다.
  • curr 가 1 이하인지 확인하고, 아니라면, l 을 증가시켜 조건을 맞춰준다.

function sw2(s) {
  let l = 0;
  let cur = 0;
  let ans = 0;

  for (let r = 0; r < s.length; r++) {
    if (s[r] === "0") {
      cur += 1;
    }

    while (cur > 1) {
      if (s[l] === "0") {
        cur -= 1;
      }

      l += 1;
    }

    ans = Math.max(ans, r - l + 1);
  }

  return ans;
}

이전 문제에서 '조건' 만 바뀐 형태이다.
right bound 를 증가시키며 윈도우 사이즈를 증가시키고, '조건' 에 안맞으면, left bound 를 늘려 윈도우 사이즈를 줄이는 것은 여전히 같다.

문제 3

정수로 이뤄진 배열 nums 이 있을 때, 배열의 원소를 모두 곱해서 k 가 넘지 않는 부분 배열(subarray)의 개수를 구하라.

ex) nums = [10, 5, 2, 6], k = 100 일 때, 답은 8 이다.

leet code 문제 링크

내가 생각한 아이디어

• 부분 배열 (subarray) 이라는 힌트를 얻었으니, 슬라이딩 윈도우 방법을 사용한다는 생각을 해볼 수 있다.
• 슬라이딩 윈도우 알고리즘에서 시간 복잡도를 줄이는 가장 중요한 요소는 제외할 부분이다. 계산할 필요 없는 부분을 정확히 생각해내서 계산하지 않는 것이다.
  • [10, 5, 2, 6] 에서 부분 배열 [10, 5, 2] 가 k(100) 보다 크거나 같다면, [10, 5, 2, 6] 은 계산할 필요가 없어진다.
  • 그 말인 즉, r 이 커졌을 때, l 이 첫 인덱스부터 시작할 필요가 없다는 얘기다.
  • l 은 마지막으로 성공했던 조합인 [5, 2] 에서 맨 앞인 5 에 위치해있어도 된다.

function sw3(nums, k) {
  // nums[i] 의 범위는 1 ~ 1000 까지인데,
  // k 의 범위는 0부터 시작이라서 1보다 작거나 같다면, 정답은 0이다.
  if (k <= 1) {
    return 0;
  }

  let c = 1; // 곱을 누적해서 가지고 있을 변수
  let ans = 0; // 정답을 저장할 변수
  let l = 0; // left bound 인덱스를 저장할 변수

  // right bound 를 1씩 증가시키며 정답을 찾는다.
  for (let r = 0; r < nums.length; r++) {
    // 곱을 누적한다.
    c = c * nums[r];

    // left bound 가 아직 right bound 위치에 도달하지 못했고,
    // 곱의 누적이 k 보다 크거나 같다면,
    // left bound 의 위치를 앞으로 한칸씩 땡기며 곱의 누적을 줄여나가본다.
    while (l <= r && c >= k) {
      c = c / nums[l++];
    }

    // 만일, 어떻게 해도 곱의 누적이 k 보다 작아지지 않았다면, 0이 더해진다.
    // 곱의 누적이 k 보다 작다면, 만들 수 있는 모든 경우의 수의 subarray 길이를 더한다.
    ans += r - l + 1;
  }

  return ans;
}

사이즈가 고정된 sliding window 문제 생각해보기

이전까지 핵심 알고리즘은 오른쪽 경계선을 늘려가며, 조건을 확인하고, 조건에 맞지 않는다면 왼쪽 경계선을 줄여나가는 것이었다. 사이즈가 고정되면, 사이즈가 고정되었다는 점 때문에 오히려 문제가 쉬워질 수도 있다. 보통 의사코드는 아래와 같이 작성한다.

// 접근법 1

function fn(arr, k):
  curr = 슬라이딩 윈도우 조건 추적에 이용되는 변수

  // 첫번째 윈도우 빌드하기
  for i in [0, k - 1]:
    curr 등을 이용해 첫번째 윈도우를 구축한다.

  ans = 정답을 저장할 변수
  for i in [k, arr.length - 1]:
    윈도우에 arr[i] 를 더한다.
    윈도우에서 arr[i - k] 를 뺀다.
    정답을 업데이트한다.

  return ans

// 접근법 2
function fn(arr, k):
  curr = 슬라이딩 윈도우 조건 추적에 이용되는 변수
  ans = 정답을 저장할 변수

  for i in range(len(arr)):
    if i >= k:
      정답 업데이트
      윈도우에서 arr[i - k] 를 뺀다.
    윈도우에 arr[i] 를 더한다.

  정답 업데이트
  return ans // 혹은 max(ans, curr)

문제 4

정수 배열 num 와 정수 k 가 주어졌을때 k 길이를 가진 부분 배열 중 가장 큰 합을 찾아라.

내 아이디어

• 길이가 k 로 고정되었기 때문에, 단순히 left bound 와 right bound 를 1씩 증가시키며 최대 값을 구해보면 될 것 같다.
• 알고리즘
  • 먼저 r 을 0 부터 k - 1 까지 증가시키며 더해나가고, 이를 c 에 담아놓는다.
  • while(r < nums.length) 라면
    • nums[l] 을 빼고 l 을 1 증가시킨다.
    • nums[r] 을 더하고 r 을 1 증가시킨다.
    • ans = Math.max(c, ans) 를 통해 정답을 업데이트한다.

function sw4(nums, k) {
  let l = 0;
  let r = 0;
  let c = 0;

  for (; r < k; r++) {
    c += nums[r];
  }

  let ans = c;

  for (; r < nums.length; r++) {
    c -= nums[l++];
    c += nums[r++];
    ans = Math.max(c, ans);
  }

  return ans;
}

모범 답안

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findBestSubarray = function (nums, k) {
  let curr = 0;
  for (let i = 0; i < k; i++) {
    curr += nums[i];
  }

  let ans = curr;
  for (let i = k; i < nums.length; i++) {
    curr += nums[i] - nums[i - k];
    ans = Math.max(ans, curr);
  }

  return ans;
};

공간이 하나 덜 필요하다.

클로징 노트

슬라이딩 윈도우는 다양한 용도가 존재한다. 여기서는 단순히 늘이고 줄이고만 해봤는데, 슬라이딩 윈도우 문제 중 많은 문제가 해시맵을 이용한다. 나중에 해시맵을 배울 때 같이 배워보자.