슬라이딩 윈도우: 겹침을 다시 계산하지 마

"배열 위 인접한 두 윈도우는 원소를 거의 다 공유해. 각각 처음부터 다시 계산하면 그 겹침을 버리는 거야. 슬라이딩 윈도우는 그걸 지켜 — 그게 O(n²) → O(n) 승리 전부야."

낭비하는 방식, 그리고 고침

k 개 연속 원소의 최대 합을 원한다고 해. 순진한 방식: 각 시작 위치마다 그 k 개 원소를 더해. 그게 n 윈도우 × k 덧셈 = O(n·k), k 가 n 따라 커지면 O(n²). 근데 이웃한 두 윈도우를 봐 — 양쪽 한 원소씩 빼고 다 겹쳐. 무차별은 그 공유된 가운데를 매번 다시 더해.

슬라이딩 윈도우가 이걸 고쳐: 첫 윈도우 합을 한 번 계산하고, 오른쪽으로 들어오는 원소를 더하고 왼쪽으로 나가는 원소를 빼서 미끄러져. 각 미끄러짐이 O(1) 이라, 전체 훑기가 O(n). 겹침을 절대 다시 계산 안 하고 — 가장자리에서만 조정해. 분할 상환 분석이랑 누적 합이랑 같은 본능이야: 이미 한 일을 다시 하지 마.

윈도우 두 맛

고정 크기 윈도우 — 윈도우가 늘 k 너비; 그냥 미끄러져. "매 k-길이 구간의 max/min/평균" 에 써.
가변 크기 윈도우 — 두 끝이 조건을 만족하려 독립적으로 움직여. 윈도우가 "충분히 유효" 할 때까지 오른쪽 가장자리를 키우고, 유효한 동안 왼쪽 가장자리를 줄여. "중복 없는 가장 긴 부분 문자열", "합 ≥ target 인 가장 작은 부분 배열" 에 써. 두 끝 다 여전히 앞으로만 움직여서, 반복문 둘처럼 보여도 여전히 총 O(n).

슬라이딩 윈도우는 연속된 범위 사이 겹침을 재사용해: 들어오는 원소 더하고, 나가는 원소 빼고. 두 포인터 다 앞으로만 움직여서, O(n²) 처럼 보이는 훑기가 O(n) 이 돼.

가변 윈도우가 왜 여전히 O(n) 인가

가변 윈도우는 중첩 반복문처럼 보여 — 바깥 포인터랑 안쪽 줄이기 반복문 — 그래서 사람들은 O(n²) 이라 가정해. 트릭은 왼쪽 포인터가 절대 뒤로 안 간다는 거야. 전체 구간에 걸쳐, 오른쪽 포인터가 n 번 전진하고 왼쪽 포인터가 많아야 n 번 전진해. 총 이동 ≤ 2n. 중첩이 아니라 총 포인터 이동을 세는 게 O(n) 임을 보는 법이야. Complexity 트랙의 그 분할 상환 추론을, 반복문 모양에 적용한 거야.

피파의 고백

가변 크기 윈도우가 처음엔 내 뇌를 깨뜨렸어 — 안쪽 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