슬라이딩 윈도우(sliding window)

효과적인 경우

• 고정된 크기의 윈도우를 사용하거나, 윈도우 크기를 동적으로 조절하여 문제해결 가능

💡 적용 예

1. 고정된 크기의 부분 배열 또는 부분 문자열을 탐색하는 문제
2. 연속적인 부분배열 또는 부분 문자열의 특정 조건을 만족하는 경우 찾기

개요

• 고정된 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘
• 네트워크 사용되던 알고리즘을 문제 풀이에 응용한 경우

• 투 포인터와 슬라이딩 윈도우의 알고리즘의 차이를 알고 적절하게 사용

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

  

• 참고 : 슬라이딩 윈도우는 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하는 네트워크 용어
  • 네트워크에서 패킷을 전송할 때 고정사이즈가 옆으로 이동하면서 그 다음 패킷들을 전송하는 방식

시간복잡도

O(n)

• 고정된 슬라이딩 윈도우나 가변 슬라이딩 윈도우 모두 각 요소를 최대 한번씩만 처리하기 때문에 O(n)의 시간복잡도를 갖는다.

사용예

---

• 참고자료
  • Two pointer (투 포인터)