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

1) 슬라이딩 윈도우 알고리즘 개념

고정된 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 활용해 문제를 풀이하는 알고리즘을 말합니다. 즉, 이미 한번 구했던 값을 재사용하는 것이 핵심입니다. 

 

배열이나 리스트의 요소의 일정 범위의 값을 비교하거나 연산할 때 사용하면 매우 유용합니다. 

 

문제풀이시 주로 사용되는 경우에는 배열과 그 부분배열을 어떤 조건하에서 계산하는 경우에 주로 사용됩니다. 예를 들어 구간 합 구하기, 부분 문자열 구하기등에 활용될 수 있습니다.

 

2) 슬라이딩 윈도우 동작원리

슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만, 부분 배열의 길이(크기)가 고정적 입니다.

• 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점을 가지고 있습니다.
• 투 포인터 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하지만 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점을 가지고 있는 것을 확인할 수 있습니다.

교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법을 통해 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용합니다. ⭐️⭐️⭐️

 

슬라이딩 윈도우 알고리즘은 투 포인터(two pointers)알고리즘과 연동하여 많이 쓰입니다.

• 투 포인터(two pointers)알고리즘 : 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 원하는 값을 얻는 형태의 알고리즘
• 투 포인터 알고리즘은 부분 배열의 길이가 가변적 이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 잡기 때문에 포인터 변수가 2개일 필요가 없습니다.
• 즉, 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝이 어딘지 알 수 있습니다.