[알고리즘] 슬라이딩 윈도우

밀어! 밀어! 밀라고!
(따라하시면 안됩니다.)

📃 예시 문제

[백준] 20437 - 문자열 게임 2

비슷한 알고리즘 "투 포인터"은 풀어봤는데...
그렇게 풀어봤다가 시간초과나는 기이한 문제였다.

어...? 이게 아닌가...?
하고 밑에 힌트를 보니

? 이게 무슨 알고리즘이야
갑자기 창문을 왜 밀어...?

📍설명

위키백과엔 이렇게 나와있다.
두 개의 네트워크 호스트간의 패킷의 흐름을 제어하기 위한 방법
이거 아닙니다.

슬라이딩 윈도우 (Sliding window)
일정한 크기의 배열이나 리스트를 이동시키며 문제를 해결하는 기법

투 포인터는 두 개의 포인터를 사용하여 배열이나 리스트의 특정 구간을 탐색하는 기법이다.
저 두개의 포인터가 자유롭게 움직인다.
(자세한건 요기에)

슬라이딩 윈도우는 일정한 크기가 핵심이다.
저 맨 위에 gif의 창문처럼 움직인다.
실제로도 창문의 크기가 가변적이지 않지 않는가?

주로 연속된 부분 배열에서 최대/최소값, 특정 조건을 만족하는 구간 등을 찾는 데 사용된다.

🗂️ 최종 개념 정리

투 포인터는 두 개의 포인터가 있고, 구간의 넓이가 조건에 따라 유동적
슬라이딩 윈도우는 항상 구간의 넓이가 고정 (즉, 포인터는 하나면 충분)

근데 두 알고리즘 다,
1차원 배열을 2회 이상 탐색해야 할 경우 O(N^2)을
부분 배열을 활용하여 O(N)으로 줄일 수 있다