Sliding Window Algorithm

조건

• N개의 원소를 가지는 배열
• W의 크기를 가지는 창문(윈도우, 특정 구간...)
• 이 때, N과 W는 상수(고정 값)

Sliding Window

• 고정된 사이즈의 윈도우를 이동시키면서 윈도우 내에 있는 데이터를 이용해서 문제를 풀이하는 알고리즘
• 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝의 원소만 갱신하는 방법
• 이렇게 되면 구간합을 구할 때, 최초에만 O(W)의 시간복잡도가 걸리고 이후에는 양쪽 끝 원소만 갱신하면 되기 때문에 O(1)의 시간복잡도가 걸림
• 배열의 일정 범위의 값을 비교할 때 사용하면 매우 유용함
• 투 포인터(Two pointer)알고리즘과 연동해서 많이 사용
• 투 포인터와의 차이점은 구간의 넓이가 항상 고정되어 있다는 것

유형

• 구간합
• Anagram
• 구간 최소값

생각

구간 합을 구할 때

윈도우를 옮길때마다 구간 합을 구하려고 하면 W(윈도우의 크기)만큼 원소를 모두 더하는 작업을 일반적으로 떠올리게 된다. 이렇게 되면 N개의 원소를 가진 배열에서 W크기의 구간합을 모두 구하려고 한다면 O(N * W)의 시간 복잡도를 가진다. 하지만 슬라이딩 윈도우 알고리즘의 아이디어를 적용하게 된다면 윈도우를 옮길때마다 O(1)에 구간 합을 구할 수 있기 때문에 최종적으로 O(N)의 시간 복잡도가 걸리게 된다.

let array = [7, 4, 3, 6, 8, 6, 2, 3, 1]
let windowSize = 3

var window = array[0..<windowSize].reduce(0, +)
var answer = window

// 1. Generally
for i in stride(from: windowSize, to: array.count, by: 1) {
  window += array[i] - array[i - windowSize]  // 이 곳에서 효율성을 챙기는 것
  answer = max(answer, window)
}
print(answer)

예제

• 프로그래머스 - 추석 트래픽
• 백준 - 블로그
• LeetCode - 중복 없는 긴 문자열
• 백준 - 꿀 아르바이트