Sliding window

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

 

 

 

( 슬라이딩 윈도우 알고리즘 간단 예제 ) 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 입니다. - 이러한 규칙을 바탕으로 보면 다음 배열의 값은 전 배열에서  처음 원소를 빼고 다음에 들어올 원소를 더해주면 된다는 것을 알 수 있습니다!!