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

1. 슬라이딩 윈도우란 

배열, 문자열 또는 리스트와 같은 선형 데이터 구조에서 특정 범위나 구간을 효율적으로 처리하기 위한 기법으로,

이 알고리즘은 고정된 크기의 범위를 유지하거나 가변적인 범위를 움직이며 데이터를 처리한다.

 

부분 배열을 어떠 조건하에서 계산하는 경우, 구간 합 구하기, 부분 문자열 구하기 등에 활용하며, 

불필요한 계산을 줄이고 효율적으로 해결할 수 있게 해준다.

 

1. 윈도우

 

연속된 데이터의 부분집합으로, 일반적으로 배열의 인덱스나 문자열의 일부로 표현된다.

 

2. 윈도우의 크기

 

고정 크기 : 윈도우의 크기가 일정.

가변 크기 : 윈도우의 크기가 문제의 조건에 따라 변함

 

3. 슬라이딩

 

윈도우의 시작 또는 끝을 한 칸씩 이동하며 데이터를 처리하고,

이전 윈도우에서 계산한 결과를 활용해 중복 계산을 피한다.

 

 

2. 과정 및 코드 예

초기에 구간을 설정하고,  윈도우를 한 칸 또는 여러 칸 오른쪽으로 이동한다. 

새롭게 추가된 요소를 반영하고, 윈도우에서 벗어난 요소를 제거하낟.

이동 중에 원하는 결과를 계산

 

 

배열에서 연속 부분 구간의 합이 S 이상이 되는 가장 짧은 구간의 길이 구하기

 

 

슬라이딩 윈도우를 사용해 구간을 확장 및 축소하며 효율적으로 해결하며,

불필요한 계산을 줄이고 O(n) 시간 복잡도를 유지한다.

이중 루프로 구간을 조절하며 최적의 해를 탐색한다.