슬라이딩 윈도우
슬라이딩 윈도우란 일정한 길이를 이동시키면서 조건에 맞는 값을 찾는 알고리즘입니다.
배열에서 일정 범위의 합을 비교할 때 매우 유용한 방법으로,
값을 이동시킬 때 배열의 처음 값을 제거하고 배열의 마지막 값을 더해주기만 하면 되는데,
배열의 모든 값을 불러와서 더하는 연산을 피할 수 있어 매우 효율적입니다.
양 옆에 지점을 둔다는 점에서 투 포인터와 비슷한 점이 있지만,
투 포인터는 범위가 유동적으로 변하지만, 슬라이딩 윈도우는 범위가 고정되어 있다는 점이 차이점입니다.
다음은 투 포인터를 그림으로 표현한 예시입니다.
조건에 따라 범위가 유동적으로 변경되는 것을 볼 수 있습니다.
다음은 슬라이딩 윈도우를 그림으로 표현한 예시입니다.
범위는 항상 고정되어 있고, 배열은 좌우로만 이동합니다.
728x90
'CS > 알고리즘 (Algorithm)' 카테고리의 다른 글
| [알고리즘] 누적 합 (0) | 2023.09.08 |
|---|---|
| [알고리즘] 투 포인터(Two Pointer) (0) | 2023.09.01 |
| [알고리즘] 메모이제이션(Memoization) (0) | 2023.08.18 |
| [알고리즘] LCS (0) | 2023.08.14 |
