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

슬라이딩 윈도우 알고리즘이란?

• 연속적인 부분 배열 혹은 구간을 처리하거나 분석하는데 유용한 알고리즘 기법.
• 고정된 크기의 윈도우를 배열이나 리스트와 같은 데이터 구조 상에서 일정한 간격으로 이동시키며 문제를 해결.
• 윈도우를 한 칸씩 이동시키는 과정에서 중복 계산을 피하고 필요한 계산을 최적화하여 효율적으로 문제를 해결할 수 있는 장점이 있음.

기본 아이디어

1. 초기에 윈도우의 크기를 설정하고, 첫 번째 윈도우 내부의 요소들을 초기화.
2. 윈도우를 한 칸씩 오른쪽(왼쪽) 으로 이동시키면서 각 위치에서 윈도우 내부의 요소들을 처리.
3. 윈도우를 이동시키는 동안 추가적인 요소를 윈도우에 포함시키거나 제외.
4. 문제의 조건에 따라 윈도우 내부의 요소들을 이요해 원하는 결과를 계산.

사용처

• 연속적인 부분 배열의 최대, 최소, 합 등을 계산하는 문제.
• 특정 조건을 만족하는 부분 배열을 찾는 문제.
• 두개의 배열이나 문자열에서 공통된 패턴을 찾는 문제.