[알고리즘] 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우

 

슬라이딩 윈도우란 일정한 길이를 이동시키면서 조건에 맞는 값을 찾는 알고리즘입니다.

 

배열에서 일정 범위의 합을 비교할 때 매우 유용한 방법으로,

값을 이동시킬 때 배열의 처음 값을 제거하고 배열의 마지막 값을 더해주기만 하면 되는데,

배열의 모든 값을 불러와서 더하는 연산을 피할 수 있어 매우 효율적입니다.

 

양 옆에 지점을 둔다는 점에서 투 포인터와 비슷한 점이 있지만,

투 포인터는 범위가 유동적으로 변하지만, 슬라이딩 윈도우는 범위가 고정되어 있다는 점이 차이점입니다.

 

 

다음은 투 포인터를 그림으로 표현한 예시입니다.

 

투 포인터

조건에 따라 범위가 유동적으로 변경되는 것을 볼 수 있습니다.

 

 

 

다음은 슬라이딩 윈도우를 그림으로 표현한 예시입니다.

슬라이딩 윈도우

범위는 항상 고정되어 있고, 배열은 좌우로만 이동합니다.