- 연속된 구간(subarray, substring 등)을 효율적으로 탐색하는 알고리즘 기법
- 범위를 유지한 채 좌우로 “창문”을 미끄러뜨리며 전체 데이터를 확인
1. 특징
- 시간복잡도:
O(n)
- 반복적인 계산 없이 이전 결과 재사용
- 고정 길이 or 가변 길이 구간 모두 가능
2. 적용 예시
가. 문제: 배열에서 연속된 k개의 숫자 합 중 최대값 구하기
int[] arr = {1, 3, 2, 5, 1, 1, 2};
int k = 3;나. 슬라이딩 윈도우 풀이
int sum = 0;
for (int i = 0; i < k; i++) {
sum += arr[i]; // 초기 윈도우
}
int max = sum;
for (int i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k]; // 앞 빼고 뒤 더하기
max = Math.max(max, sum);
}- 윈도우를 한 칸씩 오른쪽으로 이동
- 맨 앞 값 제거 + 새 값 추가
다. 시각적 흐름
3. 자주 쓰이는 유형
- 최댓값/최솟값 구간 합
- 특정 조건 만족하는 최장/최단 부분 문자열
- 누적합 기반 문제
Share article