211. Sliding Window

투 포인터의 특수한 경우인 슬라이딩 윈도우(Sliding Window)에 대해 알아보기로 한다.

---

슬라이딩 윈도우는 투 포인터에서 양쪽 포인터가 같은 간격을 유지하면서 일정한 속도로 이동하는 구조로 마치 고정된 크기의 윈도우(Window)가 움직이는 것과 유사하기 때문에 이런 이름이 붙었다. 원래 네트워크 쪽 용어인데 이제는 알고리즘 용어로도 많이 쓰인다.

 

포인터의 이동에 제약이 있다는 점을 제외하면 나머지 부분은 일반적인 투 포인터와 동일하다. 대신 이런 제약 때문에 구현이 더 간단해지기도 하고, 누적 합 등을 이용해 포인터를 대체할 수 있는 경우도 많다. 연습문제를 통해 살펴보기로 하자.

 

[연습문제]

 

BOJ 24499. blobyum (Silver IV)

슬라이딩 윈도우를 적용하는 문제들은 이 문제처럼 원형 구조가 등장하는 빈도가 다른 유형에 비해 높다. 원형 구조를 슬라이딩 윈도우로 처리할 때는 일직선으로 펴서 두 번 이어붙이고 처리하면 편한데, 한 바퀴를 넘는 구간을 고려하는 등의 실수를 하지 않도록 주의해야 한다. 이 문제도 그런 방식으로 누적합을 구하면 쉽게 풀 수 있다.

 

BOJ 2559. 수열 (Silver III)

24499번을 선형 구조에서 풀면 된다. 그러면 티어는 같거나 이게 더 낮아야 할 것 같은데...

 

BOJ 2531. 회전 초밥 (Silver I)

누적합을 쓰기 어려운 문제이다. 슬라이딩 윈도우로 포인터가 이동할 때마다 구간에 존재하는 초밥들의 카운팅 정보를 바꿔 주면서 가장 종류가 다양해지는 경우를 찾는다. 이 문제를 풀었다면 제한이 더 큰 15961번도 풀어 보자.

 

→ solved.ac tag: sliding_window