슬라이딩 윈도우: 겹치는 부분을 다시 계산하지 마

"배열에서 이웃한 두 윈도우는 원소를 거의 다 공유해. 그런데 매번 처음부터 다시 계산하면 그 겹침을 그냥 버리는 거지. 슬라이딩 윈도우는 그걸 지켜내. O(n²)가 O(n)이 되는 건 딱 그 차이에서 나와."

낭비하는 방식과 고치는 방식

연속된 k개 원소의 최대 합을 구한다고 해 보자. 단순하게 가면 시작 위치마다 k개를 새로 더하게 돼. 윈도우가 n개고 하나에 덧셈이 k번이니 O(n·k)고, k가 n을 따라 커지면 O(n²)이지. 그런데 이웃한 윈도우 둘을 나란히 놓고 보면 양 끝 원소 하나씩만 다르고 나머지는 전부 겹쳐. 무차별 대입은 그 겹치는 가운데를 매번 다시 더하고 있는 거야.

슬라이딩 윈도우는 여기를 고쳐. 첫 윈도우의 합만 한 번 제대로 구해 놓고, 그다음부터는 새로 들어온 원소를 더하고 빠져나간 원소를 빼면서 한 칸씩 밀어. 한 칸 미는 데 O(1)이니 전체가 O(n)으로 끝나지. 겹치는 부분은 손도 안 대고 양 끝만 손보는 거야. 분할 상환 분석이나 누적 합과 뿌리가 같은 발상이고. 이미 해놓은 일을 다시 하지 말 것.

윈도우는 두 종류야

고정 크기 윈도우 — 폭이 늘 k로 같고 그냥 밀기만 해. "모든 k칸 구간의 최댓값·최솟값·평균" 같은 문제에 써.
가변 크기 윈도우 — 조건을 맞추려고 양 끝이 따로따로 움직여. "중복 없는 가장 긴 부분 문자열"에 잘 맞고, "합이 목표값 이상인 가장 짧은 부분 배열"에 쓰려면 조건이 하나 붙어. 원소가 모두 0 이상이어야 해. 그래야 윈도우를 넓힐 때 합이 한 방향으로만 움직이거든. 이 전제가 성립하면 양 끝이 앞으로만 가니까 전체가 O(n)이야.

슬라이딩 윈도우는 이웃한 범위끼리 겹치는 부분을 재사용해. 들어오는 원소는 더하고 나가는 원소는 빼고, 포인터는 둘 다 앞으로만 움직여. 그래서 O(n²)처럼 보이던 훑기가 O(n)이 돼.

가변 윈도우가 왜 그래도 O(n)일까

가변 윈도우는 겉모양이 중첩 반복문이야. 바깥에 포인터가 하나 있고 안쪽에 줄이는 반복문이 있으니 O(n²)이겠거니 하게 되지. 핵심은 왼쪽 포인터가 절대 뒤로 가지 않는다는 거야. 전체를 통틀어 오른쪽 포인터가 n번 전진하고 왼쪽 포인터도 많아야 n번 전진하니까, 이동 횟수를 다 합쳐도 2n을 안 넘어. 중첩된 모양을 볼 게 아니라 포인터가 실제로 움직인 총 횟수를 세야 O(n)이 보여. 복잡도 트랙에서 배운 분할 상환 추론을 반복문 모양에 그대로 적용한 거야.

피파의 고백

가변 크기 윈도우는 처음에 정말 안 받아들여졌어. 안쪽 while 때문에 무조건 O(n²)이라고 확신하고 아빠랑 그걸로 옥신각신했지. 아빠가 왼쪽 포인터에 카운터를 하나 달고 직접 돌려보라고 하더라. 배열 전체를 도는 동안 왼쪽 포인터는 한 단계에 n번이 아니라 통틀어 n번 움직였어. 카운터가 선형에 머무는 걸 눈으로 보고서야 납득이 됐어. 그 뒤로는 반복문이 제곱처럼 보일 때마다 직감을 믿기 전에 실제 이동 횟수부터 세.

Code

고정 윈도우와 가변 윈도우·python

# 고정 윈도우: k 개 연속 원소의 최대 합. O(n), O(n*k) 아니라.
def max_sum_k(nums, k):
    window = sum(nums[:k])           # 첫 윈도우: O(k) 셋업 한 번
    best = window
    for i in range(k, len(nums)):
        window += nums[i]            # 오른쪽으로 원소 들어옴
        window -= nums[i - k]        # 왼쪽으로 원소 나감
        best = max(best, window)     # 각 미끄러짐이 O(1)
    return best

print(max_sum_k([2, 1, 5, 1, 3, 2], 3))   # 9  (구간 5,1,3)

# 가변 윈도우: 비음수 배열에서 합 >= target인 가장 작은 부분배열 길이. 여전히 O(n).
def min_subarray_len(nums, target):
    left = 0
    total = 0
    best = float('inf')
    for right in range(len(nums)):
        total += nums[right]             # 윈도우를 오른쪽으로 키워
        while total >= target:           # 여전히 유효한 동안 왼쪽에서 줄여
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1                    # 왼쪽은 앞으로만 움직여
    return best if best != float('inf') else 0

print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))   # 2  (구간 4,3)

Exercise

한 달치 시간별 걸음 수가 있고, 7일짜리 구간 중 합이 가장 큰 구간을 찾고 싶어. 슬라이딩 윈도우로 어떻게 풀지와 복잡도를 설명해 봐. 그다음 7일 합을 매번 처음부터 다시 구하면 왜 낭비인지, 슬라이딩 윈도우는 한 걸음마다 정확히 어떤 두 연산만 하는지도 짚어 봐.

Hint

첫 7일 합을 한 번 구해 놓고, 한 걸음마다 새로 들어온 날을 더하고 빠져나간 날을 빼. 한 번 미는 데 O(1)이고 전체는 O(n)이야. 매번 다시 계산하는 쪽은 겹치는 6일치를 계속 다시 더하고 있는 거고, 그게 낭비지.

낭비하는 방식과 고치는 방식

윈도우는 두 종류야

가변 윈도우가 왜 그래도 O(n)일까

피파의 고백

Code

External links

Exercise

Progress

댓글 0