[Algorithm] 슬라이딩 윈도우(sliding window) vs 투 포인터(two pointer)

슬라이딩 윈도우(sliding window)란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다. 원래 네트워크에서 사용되던 알고리즘을 문제 풀이에 응용한 경우라고 한다. 슬라이딩 윈도우는 네트워크 용어로, 2개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하기도 하기 때문이다.

 

투 포인터와 유사하지만 이와 구분하기 위해 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 따로 구분하기도 한다.

또한, 투 포인터는 주로 정렬된 배열을 대상으로 하지만, 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다.

즉, 이름 그대로 생각하면 편하다. 투 포인터는 좌우 포인터가 자유롭게 이동하며 윈도우 사이즈가 가변적인 반면, 슬라이딩 윈도우는 고정된 윈도우 사이즈가 좌 또는 우 한쪽 방향으로만 이동해가며 배열을 탐색하는 느낌이다.

이름	정렬 여부	윈도우 사이즈	이동
투 포인터	대부분 O	가변	좌우 포인터 양방향
슬라이딩 윈도우	X	고정	좌 또는 우 단방향

이렇게 구분이 되지만, 둘 사이를 명확하게 구분하는 게 큰 의미는 없기에 자유롭게 혼용하여 풀이해도 무방하다.

 

 

 

 

 

Reference

파이썬 알고리즘 인터뷰