배열에서 Sliding Window — 초보자를 위한 사고 모델

Source: Dev.to

Sliding Window란?

Sliding window는 배열(또는 문자열)의 연속된 부분을 처리하면서 이전 계산을 재사용하는 기법입니다.
각 새로운 부분 배열에 대해 모든 것을 다시 계산하는 대신에:

1. 첫 번째 윈도우에 대한 결과를 계산한다.
2. 윈도우를 앞으로 이동시키면서 떠나는 요소를 제거하고 들어오는 요소를 추가한다.

그게 전부입니다.

Sliding Window를 언제 사용하나요?

문제에서 부분 배열 / 부분 문자열에 대해 무언가를 요구하고, 특히 다음과 같은 표현이 있을 때 사용합니다:

• “크기 K인 부분 배열”
• “길이 K인 윈도우의 최대/최소 합”

이 경우, 순진한 접근법은:

• 가능한 모든 부분 배열을 순회한다.
• 매번 모든 요소를 다시 합산한다 → O(N·K) 시간.

Sliding window를 사용하면 결과를 점진적으로 업데이트함으로써 O(N) 시간에 해결할 수 있습니다.

예시

다음 배열을 보세요:

[5, 2, 7, 1]
K = 3

첫 번째 윈도우 ([5, 2, 7]) → 합 = 14

한 단계 슬라이드 →

• 떠나는 요소: 5
• 새로운 윈도우: [2, 7, 1]
• 업데이트된 합: 14 - 5 + 1 = 10

전체를 다시 계산할 필요가 없습니다.

포인터 이동 방식

고정 크기 Sliding Window

윈도우 크기를 k라고 하자. 각 단계 i(시작은 i = k)마다:

• 떠나는 요소 = arr[i - k]
• 들어오는 요소 = arr[i]

별도의 “왼쪽 포인터”를 만들 필요 없이, 위의 연산이 이를 대신합니다.

샘플 코드 (C++)

double maxSumSubarray(vector nums, int k) {
    int windowSum = 0;

    // first window
    for (int i = 0; i (maxSum) / k;
}

위 단계들을 명확히 설명할 수 있다면, 어떤 언어로든 동일한 로직을 구현할 수 있습니다.

이해도를 확인하기 위한 예시 입력

nums = [1, 12, -5, -6, 50, 3]
k = 4

윈도우는 다음과 같습니다:

1. [1, 12, -5, -6]
2. [12, -5, -6, 50]
3. [-5, -6, 50, 3]

각 슬라이드마다 하나의 요소를 제거하고 새로운 요소를 하나 추가하므로, 합(또는 다른 집계값)을 뺄셈 + 덧셈 연산만으로 업데이트할 수 있습니다. 추가적인 루프가 필요하지 않습니다.

핵심 요점

Sliding‑window 기법은 마법이 아니라, 단순히:

“떠나는 것을 빼고, 들어오는 것을 더해 이전 결과를 재사용한다.”

이렇게 함으로써 중복 계산을 피하고 많은 부분 배열/부분 수열 문제를 선형 시간 해결법으로 만들 수 있습니다.