[알고리즘] 슬라이딩 윈도우(sliding window) 알고리즘 이란?

슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 알고리즘과 유사하지만 부분 배열의 길이가 고정적이다.

고정적인 틀을 오른쪽으로 밀어 오면서  틀 안에 있는 값들을 부분배열이라고 생각하면 된다.

투 포인터 알고리즘은 두 개의 포인터를 이동하기 때문에 2개의 변수가 필요하지만 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 하기 때문에 1개의 변수만 필요하다.

 

 

 

설명

아래 노란색 칸이 3의 고정길이를 가지는 부분 배열이라 가정, 

주어진 문제가 부분 배열의 합을 구하는 것이라 하면 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에 겹치는 부분이 존재한다. 즉 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가하면 된다.

 

예시

2가지 긴 문자열이 주어지고 알파벳 2개만을 포함하는 가장 긴 문자열을 찾는 문제가 있다.

슬라이딩 알고리즘을 이용하여 풀면 파란색으로 칠해진 영역이 윈도우가 되고 이를 하나씩 밀게 되는 것이다.

 

 

 

 

 

그림의 Right를 하나씩 움직이면 되는데 Right가 C를 가리키면 다음 포함하는 문자열이 3개가 되므로 윈도우가 더 이상 확장 되지 않고 다음 윈도우로 움직인다.

 

 

 

이런식으로 이동을 하여 윈도우에 잡힌 값들이 조건에 맞는지 탐색한다. 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제를 해결할 수 있다. 

 

 

 

 

참고

• https://bbangson.tistory.com/72
• https://ramees.tistory.com/52