슬라이딩 윈도우(Sliding window)

1. 투 포인터(Two pointer)와 슬라이딩 윈도우

리스트에서 데이터에 접근할 때 한 방향으로 탐색하는 선형탐색은 매우 간단하지만 리스트의 크기가 커지게 되면 효율적이지 않다는 문제가 있다. 이를 극복할 수 있는 이진 탐색, 매개변수 탐색 등 다양한 탐색 알고리즘이 있다. 그 중, 두 개의 포인터를 이용해 범위를 좁히거나 이동시키며 탐색하는 방법을 투 포인터라고 한다. 슬라이딩 윈도우는 투 포인터 문제의 특수한 경우로, 두 포인터의 간격이 일정하게 유지되며 이동하는 문제 해결 방법이다. 두 포인터가 움직이는 것이 마치 창틀에 고정된 창문이 움직이는 것과 같아 슬라이딩 윈도우라는 이름이 붙었다.

 

2. 구현

슬라이딩 윈도우는 간단하게 구현할 수 있다. 두 개의 포인터를 지정하고 한 구간의 탐색을 끝내면 포인터를 옮긴다. 포인터를 옮기면서 구간 값을 최신화해주면 된다.

 

3. 관련 문제

13422번: 도둑

 

마지막 집과 첫번째 집이 한 구간으로 묶일 수 있다는 것과 모든 집을 다 방문할 수 있는 경우는 한 가지 뿐임을 주의하면 슬라이딩 윈도우로 쉽게 해결할 수 있는 문제

 

11003번: 최솟값 찾기

슬라이딩 윈도우의 심화버전인 모노톤 큐로 풀 수 있는 문제. 덱을 활용하면 구현은 간단하게 할 수 있다.