배열이나 문자열의 연속된 구간(창)을 한 칸씩 밀면서, 매번 처음부터 다시 계산하지 않고 빠지는 값과 들어오는 값만 반영하는 패턴. 연속 부분 배열·부분 문자열 문제를 O(n)에 푼다.
// 길이 k인 연속 구간의 최대 합
function maxWindowSum(arr: number[], k: number) {
if (arr.length < k) return null
let sum = 0
for (let i = 0; i < k; i++) sum += arr[i] // 첫 창
let max = sum
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k] // 오른쪽 하나 더하고 왼쪽 하나 뺀다
max = Math.max(max, sum)
}
return max
}- 최댓값을 0 같은 임의의 값으로 시작하면 음수만 있는 배열에서 틀린다. 첫 창의 합으로 시작한다
- 고정 크기 창(Fixed-Size Window): 위처럼 길이가 정해진 경우
- 가변 크기 창(Variable-Size Window): "중복 없는 가장 긴 부분 문자열"처럼 조건을 만족하는 동안 오른쪽을 늘리고, 깨지면 왼쪽을 줄인다. 창 안의 상태는 빈도표나
Set으로 관리한다 - 창의 양끝을 가리키는 투 포인터의 한 형태다
네트워크의 흐름 제어(Flow Control)나 시간 창 단위의 요청 제한(요청 제한 (Throttling))도 같은 이름의 아이디어를 쓴다. 다른 패턴은 알고리즘 문제 풀이 접근법.