슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)에 대해 이야기합니다. 브루트포스(Bruteforce, 완전 탐색)와 비교한 코드 조각을 기입해뒀습니다. 슬라이딩 윈도우로 풀 수 있는 백준 문제도 끝에 첨부합니다.
"슬라이딩 윈도우를 가볍게 이해하기"가 목표라면 도움이 되는 문서입니다. 

 

---

 

슬라이딩 윈도우(Sliding Window)는 "고정된 크기 또는 가변 크기의 윈도우(부분 구간)를 한 칸씩 이동하면서, 이전 계산 결과를 활용하여 중복 연산을 줄이는 기법"입니다.

윈도우는 말 그래도 "구간"입니다. 중복 연산을 줄이는 기법이란 건, 아래 예제에서 얘기할 브루트 포스(Bruteforce)과 비교하면 이해할 수 있습니다.

 

슬라이딩 윈도우는 연속된 배열의 합이나 특정 패턴을 구할 때 사용됩니다.

 

---

 

 

특정 패턴을 구할 때, 브루트포스와 슬라이딩 윈도우의 차이를 비교한 직관적인 코드 조각입니다.

 

["A", "B", "A", "B", "A", "B", "A"] //array

 

// Java 기준 작성
bruteForce = array[0] + array[1] + array[2]
bruteForce = array[1] + array[2] + array[3]

 

그러니까,  매번 새롭게 값을 계산하는 게 아니라

* 여기서 array[1] + array[2] 부분이 중복 연산이 되는 것입니다.

* 브루트포스, 시간복잡도 O(N^K)

* 이때 N은 전체 문자열의 길이, K는 윈도우의 길이입니다. 

* 즉, 문자열 길이 N개 각각 K만큼 bruteForce를 새로 생성하기 때문에 O(N^K) 입니다.

 

slidingWindow = array[0] +  array[1] + array[2]
slidingWindow = slidingWindow.substring(1) + array[3];

 

기존 값을 활용하면서 필요한 부분만 업데이트하는 게 슬라이딩 윈도우의 핵심입니다.

* substring(1)은 첫 번째 문자(인덱스 0)를 제거한 뒤 나머지 부분을 반환

* 슬라이딩 윈도우, 시간복잡도 O(N)

* substring도, +array[3]도 모두 연산이지만 새로 생성하는 것보다 적은 연산량이 듭니다. 

 

---

 

https://www.acmicpc.net/problem/5525 슬라이딩 윈도우를 통한 패턴 찾기를 익히기 위한 추천 문제