Sliding Window

Sliding Window란?

• N개의 원소를 갖는 배열, W의 넓이를 가지는 창문이 있다고 가정하자.
• 창문을 왼쪽부터 시작하여 한 칸씩 오른쪽으로 이동
• 매 순간 창문 안에서의 정보 유출이 필요하다.

Two pointer vs Sliding Window

• 일반적으로 고정된 크기의 윈도우를 사용하는 경우를 Sliding Window라고 구분한다.
• 주로 정렬된 배열을 사용하는 투포인터와 달리, 슬라이딩 윈도우는 정렬 여부에 관계없이 활용한다.
  

ex1. 구간합 문제

N개의 숫자, 창문의 크기 W가 주어졌을 때, 왼쪽부터 W개씩 연속 합을 모두 구하라.

• 기존에는 모든 창문 위치마다 O(W)에 합을 구해서 전체가 O(NW)의 시간 복잡도를 가진다.

• Sliding Window를 적용한다면?

  • 맨 처음 창문에 대해서만 O(W)이고, 이후 한 칸씩 밀 때에는 맨 앞의 숫자를 빼고 뒤의 숫자를 더해주면 되기 때문에 O(1)에 구간합을 구할 수 있다!
  • 즉, 전체 시간 복잡도는 O(N)이 된다.

• Sliding Window의 기본 아이디어

  • Window 한 칸 옮기면, (W-1)칸은 겹친다!
  • 겹치는 구간을 최대한 써먹는 방향으로 나아가자

• 첫번째 창문 안에 있는 숫자의 합 = S, 맨 앞의 숫자 = A

  • 두번째 창문 안에 있는 숫자의 합 = S'
  • S' = S - A + B (숫자 하나만 빼고 더해주면 된다)

ex2. Anagram 문제

문자열 S1, S2가 주어진다. S2의 부분 문자열 중, S1과 anagram 관계인 것의 개수를 구하라.

• Anagram: 알파벳의 구성은 유지한 채, 순서만 뒤바뀐 단어 관계

# s2에서 s1를 포함하는 부분은 4군데
s1 = abr
s2 = abradacadabra

• 창문을 옮길 때마다 W개를 전부 다 더하지 말고, 이전 결과를 써먹자

알파벳 구성: ..., c1(t1), ..., c2(t2), ...
알파벳 구성: ..., c1(t1-1), ..., c2(t2+1), ...

• 모든 창문의 위치마다 알파벳 개수를 세면 O(W) 라는 시간을 소모하지만, Sliding Window를 적요하면 알파벳 개수 업데이트에 드는 시간을 O(1)로 줄일 수 있다!

관련 문제
BOJ_11003