[알고리즘] Range: Sliding Window

1. Sliding Window

• 선형 자료구조에서 subarray를 찾는 알고리즘 입니다.
• 일정한 크기의 구간을 움직여 찾습니다.

 

동작 원리

윈도우 설정

• 초기 윈도우 구간을 설정함

 

윈도우 이동

• 한 번에 한 요소씩 이동시킴 (왼쪽 끝 제거 + 오른쪽으로 이동)

 

조건 확인

• 각 윈도우가 특정 조건을 만족하는지 확인

 

장점

성능

• 슬라이딩 윈도우를 사용하면 O(n) or O(n log n) 
• 브루트 포스일 경우, O(n^2)

 

메모리 효율성

• in-place 알고리즘 (새로운 배열 생성 X)

 

 

2. 문제

subarray

• Minimum Size Subarray Sum (문제) (해설)
• Longest Substring Without Repeating Characters (문제) (해설)