[Algorithm] 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)

 

• 슬라이딩 윈도우 알고리즘은 투 포인터와 유사하지만, 부분 배열의 길이를 고정해서 탐색하는 방법
• 투 포인터와 달리 두 개의 포인터 변수를 사용하지 않고, 고정적인 부분 배열의 크기와 한 개의 포인터 변수를 알고 있다면, 부분 배열의 양끝의 연산으로 정확한 값을 도출해낼 수 있다.

[1, 10, 3, 2, 23, 10, 12] 라는 배열이 주어졌을 때 예시

배열 안에서 네 개의 연속된 수열의 최댓값을 찾는다고 가정했을 때,

 ↓         ↓
[1, 10, 3, 2, 23, 10, 12] sum = 1 + 10 + 3 + 2

    ↓         ↓
[1, 10, 3, 2, 23, 10, 12] sum = 10 + 3 + 2 + 23 (1을 빼주고, 23을 더해준 값) 

        ↓         ↓
[1, 10, 3, 2, 23, 10, 12]

           ↓          ↓
[1, 10, 3, 2, 23, 10, 12]


최초 길이의 값을 변수로 저장하고, window를 움직일때 마다, 양 끝 값을 더하고, 빼주기만 하면 된다.

 

연습문제

https://www.acmicpc.net/problem/21921

21921번: 블로그