슬라이딩 윈도우 기법 (투 포인터)

"연속된 구간"에 대한 질문은, 구간을 매번 처음부터 다시 세지 말고 한 칸 밀 때 나간 원소만 빼고 들어온 원소만 더하면 된다. 겹치는 계산을 재활용해 O(n·k)를 O(n)으로 낮추는, 코딩 테스트 단골 패턴.

1. 고정 크기 창 — "연속한 k개의 최대 합"

길이 k인 모든 연속 구간의 합 중 최댓값을 찾는다. 순진하게 풀면 구간마다 k번씩 더해 O(n·k). 슬라이딩 윈도우는 창을 오른쪽으로 한 칸 밀 때

덧셈·뺄셈 딱 2번이면 되므로 전체가 O(n). 아래에서 초록은 새로 들어온 칸, 빨강은 창에서 빠지는 칸이다.

2. 가변 크기 창 — "합이 S 이상인 가장 짧은 구간"

이번엔 창의 크기가 정해져 있지 않다. 포인터 두 개(left, right)로 창을 관리한다.

• 확장: right를 한 칸 늘리고 새 원소를 합에 더한다.
• 수축: 합이 S 이상이면, 길이를 기록하고 left를 당겨 창을 줄인다 (더 짧은 답을 노린다).
• 두 포인터 모두 되돌아가지 않으므로 각각 최대 n번 전진 → 전체 O(n).

3. 문자열 창 — "중복 없는 가장 긴 부분문자열"

같은 아이디어를 문자열에 적용한다. right가 만난 글자가 창 안에 이미 있으면, 그 글자를 만날 때까지 left를 당겨 창에서 중복을 몰아낸다. 창은 항상 "서로 다른 글자들"만 담는다.

4. 코드로 정리

고정 창 — 최대 구간 합

def max_window_sum(arr, k):
    win = sum(arr[:k])                 # 첫 창은 한 번만 직접 계산
    best = win
    for r in range(k, len(arr)):
        win += arr[r] - arr[r - k]     # 들어온 것 +, 나간 것 -
        best = max(best, win)
    return best                          # 전체 O(n)

가변 창 — 합 ≥ S 인 최단 길이

def shortest_subarray(arr, S):
    left = 0; win = 0; best = float('inf')
    for right in range(len(arr)):
        win += arr[right]                    # 창 확장
        while win >= S:                       # 조건 만족 → 최대한 수축
            best = min(best, right - left + 1)
            win -= arr[left]
            left += 1
    return best if best != float('inf') else 0

5. 언제 쓸 수 있나 / 없나