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

( 슬라이딩 윈도우 알고리즘 간단 예제 )
1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 구한다고 가정해보면 아래 5가지의 경우의 수가 나온다.

[1, 2, 3], 4, 5, 6, 7
1, [2, 3, 4], 5, 6, 7
1, 2, [3, 4, 5], 6, 7
1, 2, 3, [4, 5, 6], 7
1, 2, 3, 4, [5, 6, 7]

다음으로 합을 계산하는 고정된 크기의 배열의 변화를 보면 [1,2,3] => [2,3,4] => [3,4,5] ... => [5,6,7]이다. 그렇다면 어떻게 최소한의 계산으로 다음 배열의 합을 구할 수 있을까?

- 먼저 처음 배열 [1,2,3] 의 합을 구한다. == 6
- 다음 배열은 [2,3,4]는 [1,2,3] 배열에서 맨 앞 값이 빠지고, 그다음 값인 4가 들어온 모습이다. 따라서 합은 (6-1+4) == 9 이다.
- 이러한 규칙을 바탕으로 보면 다음 배열의 값은 전 배열에서  처음 원소를 빼고 다음에 들어올 원소를 더해주면 된다는 것을 알 수 있다.

 

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.
• 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법이다.
• 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용하다.
• 투 포인터(two poitners) 알고리즘과 연동하여 많이 쓰인다.
  * 1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 원하는 값을 얻는 형태

위 이미지를 참고하여 보면, 투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하며, 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점이 있다.

 

 

슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트) (tistory.com)