Sliding Window (슬라이딩 윈도우)

Sliding Window (슬라이딩 윈도우)

고정 또는 가변 크기의 윈도우를 배열 위에서 한 칸씩 이동시키며 윈도우 내 정보를 효율적으로 갱신하여 연속 부분 배열/문자열 문제를 O(N)에 해결하는 기법

목적: 연속 구간 문제, 선형 시간 최적화, 부분 문자열/배열 처리

특징: 윈도우 이동, 점진적 갱신, O(N) 시간, 이전 결과 재활용

유형

• •고정 크기: 윈도우 크기 K 고정, 각 위치의 합/최대/최소 계산
• •가변 크기: 조건 만족하는 최소/최대 윈도우 찾기

고정 크기 윈도우

• •초기: 첫 K개 원소의 합/값 계산
• •이동: 새 원소 추가, 빠지는 원소 제거, O(1) 갱신
• •예: 크기 K 연속 부분 배열 최대 합

가변 크기 윈도우

• •right 포인터 확장하며 조건 검사
• •조건 불만족 시 left 포인터 수축
• •예: 합이 S 이상인 최소 길이 부분 배열

활용 자료구조: Deque(최대/최소), 해시맵(문자 빈도), 카운터

시간 복잡도: O(N), 각 원소는 최대 2번 처리(추가/제거)

공간 복잡도: O(1) ~ O(K) (윈도우 크기 또는 알파벳 크기)

장점: 선형 시간, 효율적 갱신, 직관적

단점: 연속 구간에만 적용, 복잡한 조건 시 구현 어려움

적용사례: 최대 합 부분 배열, 문자열 애너그램, 중복 없는 최장 부분문자열

비교: Sliding Window(O(N)/연속) vs Prefix Sum(O(N)/구간합) vs Segment Tree(O(log N)/동적)

연관: Two Pointers, Deque, 구간 문제, 문자열