부분 배열 합 문제는 알고리즘 코딩테스트에서 자주 마주치는 형태다. brute force 로 모든 부분 배열을 보면 O(N²) 이라 큰 입력에서 시간을 못 맞춘다. 슬라이딩 윈도우와 누적합 두 도구가 이 문제를 O(N) 으로 환원한다. 그런데 두 도구는 같은 자리에서 쓰이는 게 아니다. 입력에 음수가 섞이거나 “합이 정확히 K” 같은 등식 조건이 붙으면 슬라이딩이 깨지고 누적합 + 해시 영역으로 도구가 바뀐다. 선택은 결국 단조성 여부 한 줄로 갈린다.

슬라이딩 윈도우

슬라이딩 윈도우는 left 와 right 두 인덱스를 함께 움직이며 구간을 좁히거나 넓혀 답을 찾는 사고다. right 가 다음 원소를 윈도우에 포함하고, 조건이 깨지면 left 가 전진하여 윈도우를 축소한다. 각 원소가 윈도우에 들어오고 나가는 횟수가 정확히 두 번이라 전체 O(N) 이다.

세 가지 변형이 자주 등장한다.

  • 가변 슬라이딩 — 윈도우 크기가 답에 따라 변한다. right 를 늘리며 valid 상태를 유지, 깨지면 left 를 줄여 회복한다.
  • 고정 슬라이딩 — 윈도우 크기 K 가 미리 정해져 있다. right 가 한 칸 들어오면 right - K 가 한 칸 나간다.
  • 양 끝 투 포인터 — 정렬된 배열에서 left 와 right 가 양 끝부터 안쪽으로 좁혀온다. 두 원소 합 또는 조합 문제에서 자주 쓰인다.

가변 슬라이딩의 골격은 거의 같은 모양으로 옮겨붙는다.

def min_subarray_len(nums, target):
    left = 0
    window_sum = 0
    answer = float("inf")

    for right in range(len(nums)):
        window_sum += nums[right]

        while window_sum >= target:
            answer = min(answer, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return answer if answer != float("inf") else 0

위 코드는 LC 209, 합이 target 이상인 가장 짧은 부분 배열 길이를 구하는 문제다. valid 정의는 window_sum >= target 하나뿐이고, 그 정의가 정확하면 골격은 다른 문제에도 같은 모양으로 옮겨간다. 중복 없는 최장 부분 문자열이면 len(seen) == right - left + 1, 0 을 K 개까지 뒤집을 수 있을 때 1 의 최장 구간이면 zero_count <= K 가 valid 정의가 된다.

슬라이딩이 단조성 위에서 동작하는 이유

슬라이딩 윈도우는 한 가지 전제에 기댄다. right 가 늘어나면 윈도우 상태가 단조적으로 변한다는 것이다. 양수 합 문제라면 right 가 새 원소를 받을 때 window_sum 이 항상 증가하고, left 가 빠지면 항상 감소한다. 이 단조성이 있어야 “조건이 깨지면 left 를 끝까지 밀고 갈 때까지 이전 left 위치를 다시 고려할 필요가 없다” 는 결정이 정당해진다.

음수가 섞이면 이 전제가 깨진다. right 가 음수 원소를 받아도 window_sum 이 줄 수 있고, left 가 양수를 떠나도 합이 늘 수 있다. 어떤 left 가 답이 될지 단조적으로 판단할 수 없으니 슬라이딩 골격이 그대로 동작하지 않는다.

비슷한 이유로 “합이 정확히 K” 형태도 슬라이딩의 영역이 아니다. 부등식 >= K 라면 윈도우가 너무 크면 줄여서 정확히 맞춰갈 수 있지만, 등식은 한 칸 차이로 놓치면 회복 경로가 없다.

누적합 + 해시

단조성이 깨진 영역은 누적합 + 해시로 넘어간다. prefix[i] 를 nums[0..i-1] 의 합으로 정의하면 부분 배열 nums[l..r] 의 합은 prefix[r+1] - prefix[l] 하나의 뺄셈으로 환원된다. “합이 정확히 K 인 부분 배열의 개수” 문제는 prefix[r+1] - prefix[l] == K, 즉 prefix[l] == prefix[r+1] - K 인 이전 prefix 의 개수로 환원된다. 이전 prefix 들을 해시맵에 카운트로 쌓아두면 매 r 마다 O(1) 조회로 답이 누적된다.

def subarray_sum(nums, k):
    prefix_count = {0: 1}
    prefix_sum = 0
    answer = 0

    for x in nums:
        prefix_sum += x
        answer += prefix_count.get(prefix_sum - k, 0)
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1

    return answer

두 곳이 corner case 발화점이다. prefix_count = {0: 1} 초기값은 “배열 시작부터 합이 정확히 K 인 경우” 를 잡기 위한 sentinel 이다. 그리고 조회와 저장의 순서가 중요하다. 현재 prefix 를 먼저 저장한 뒤 조회하면 자기 자신과의 차이까지 답으로 세는 오답이 발생한다. 항상 조회를 먼저, 저장은 그다음이다.

도구 선택

두 도구의 선택은 입력 성질 두 가지로 갈린다.

flowchart TD
    A[부분 배열 합 문제] --> B{음수가 있나}
    B -->|예| D[누적합 + 해시]
    B -->|아니오| C{합이 정확히 K}
    C -->|예| D
    C -->|아니오| E[슬라이딩 윈도우]
    E --> F{윈도우 크기 고정}
    F -->|예| G[고정 슬라이딩]
    F -->|아니오| H[가변 슬라이딩]

슬라이딩 윈도우가 적합한 경우:

  • 입력이 양수만 가능할 때
  • 조건이 부등식 (>= K, <= K) 일 때
  • 윈도우 상태가 단조적으로 변할 때 (합, 카운트, 집합 크기 등)

누적합 + 해시가 적합한 경우:

  • 입력에 음수가 섞일 때
  • 합이 정확히 K 같은 등식 조건일 때
  • 구간 합 정적 쿼리가 여러 번 들어올 때

실무에서 자주 마주치는 형태는 “양수 + 부등식 → 슬라이딩, 음수 또는 등식 → 누적합” 이다. 라이브 코딩에서 1초 안에 어느 도구로 갈지 결정해야 하는 갈림이다.

부분 배열 합 문제에서 brute force O(N²) 를 O(N) 으로 환원하는 길은 두 갈래다. 양수와 부등식이 만나는 자리에서는 슬라이딩 윈도우가 단조성에 기대어 윈도우를 좁히고 넓힌다. 음수가 끼거나 합이 정확히 일치해야 하는 자리에서는 단조성이 깨지고 누적합 + 해시로 도구가 바뀐다. 두 도구의 골격은 닮았지만, 어느 도구가 맞느냐는 입력에 단조성이 살아 있는지로 결정된다.

참고