sliding-window 기법이란 무엇인가요?

Question

IT Interview Practice · Accepted Answer

**Sliding-window** 기법은 배열이나 문자열 위에 연속된 범위(윈도우)를 유지하고, 처음부터 다시 계산하는 대신 윈도우를 미끄러뜨려 많은 부분 배열/부분 문자열 문제를 **O(n)**으로 해결합니다.

## 개념

오른쪽 끝을 이동하여 윈도우를 확장하고, 제약이 위반되면 왼쪽 끝을 이동하여 축소합니다. 다시 스캔하는 대신 이전 계산을 재사용합니다.

## 예시: 크기 k인 임의 윈도우의 최대 합

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # 첫 윈도우의 합
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # 새 값 더하고 오래된 값 뺌
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## 복잡도

- **시간:** O(n) — 각 원소가 윈도우에 한 번 들어오고 한 번 나갑니다.
- **공간:** 고정 윈도우는 O(1), 내용을 추적할 때는 O(k).

## 언제 사용하나 / 함정

"속성 X를 만족하는 가장 긴/가장 짧은/최대 부분 배열" 문제에 사용하세요. **가변** 윈도우의 경우 왼쪽 포인터를 전진시켜 제약을 복원합니다. 경계 원소를 더하거나 뺄 때 off-by-one 오류를 주의하세요.

## 왜 중요한가

Sliding window는 중복 작업을 제거하여 O(n·k) 재계산을 한 번의 순회로 바꿉니다.

면접에 끊임없이 등장하는 부분 문자열과 부분 배열 문제의 핵심 패턴입니다.

재계산 대신 이전 결과를 재사용한다는 통찰은 스트리밍과 실시간 데이터로 일반화됩니다.

개념

예시: 크기 k인 임의 윈도우의 최대 합

관련 질문

복잡도

언제 사용하나 / 함정

왜 중요한가