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

슬라이딩 윈도우란 ??

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 매우 유용하다.

원래 네트워크에서 사용되던 알고리즘을 문제풀이에 응용한 개념

투 포인터와 비슷하지만 이와 구분하기 위해 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 구분하기도 한다. 또한 주로 정렬된 배열을 대상으로 하는 투 포인터와 달리 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다는 차이가 있다.

투 포인터와 함께 슬라이딩 윈도우는 알고리즘 문제 풀이에 유용하게 자주 사용되는 중요한 기법이기 때문에 잘 알아둘 필요가 있다.

투포인터는 위와 같이 윈도우 사이즈가 가변적이며 좌우 포인터가 자유롭게 이동할 수 있는 방식인 반면,

슬라이딩 윈도우는 [1, 3, 4, 2, 5] 와 같이 정렬되어 있지 않은 배열에도 적용할 수 있습니다.

윈도우 사이즈는 고정이며, 좌 또는 우 한쪽 방향으로만 이동합니다. (실무에서는 형태만 남기고 섞어쓰기도함)

네트워크 슬라이딩 윈도우: 2개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지정하는 네트워크 용어입니다. 네트워크에서 패킷을 전송할 때 고정 사이즈의 윈도우가 옆으로 이동하면서 그 다음 패킷을 전송하는 방식을 말하는데, 지금까지 설명한 슬라이딩 윈도우 알고리즘의 행동패턴과 동일합니다.

출처: 📚 파이썬 알고리즘 인터뷰