Sliding window
슬라이딩 윈도우
같은 크기의 구간을 한 칸씩 옮겨요
연속한 3개 원소의 최대 합을 구해요
현재 구간 합0
지금까지 최대 합아직 없어요
현재 위치비교 대상확인한 값
예제 코드
C++
<vector> <algorithm>int max_window(const std::vector<int>& a, int k) { int total = 0; for (int i = 0; i < k; ++i) { total += a[i]; } int best = total; for (int right = k; right < static_cast<int>(a.size()); ++right) { total += a[right] - a[right - k]; best = std::max(best, total); } return best;}Python
def max_window(a, k): total = sum(a[:k]) best = total for right in range(k, len(a)): total += a[right] - a[right - k] best = max(best, total) return best시작하기
창의 크기를 정해요
연속한 3개 원소의 합 중 가장 큰 값을 찾아요. 창의 크기는 끝까지 같아요.
사용 조건
연속한 k개 값의 합 중 최댓값을 구하는 예제예요. 이전 구간의 합을 재사용해 새 구간을 빠르게 계산해요.
먼저 알아두면 좋아요
배열과 반복문을 알고 시작해요. 창의 크기 k는 1 이상, 배열 길이 이하여야 해요.
동작 원리
첫 k개 원소의 합을 구해요. 그 값을 현재 합과 지금까지의 최댓값으로 저장해요.
창을 한 칸 옮길 때 빠지는 왼쪽 값을 빼고 새로 들어오는 오른쪽 값을 더해요. 매번 k개를 모두 다시 더하지 않아요.
- 시간
- O(n) · 각 원소를 넣고 빼는 일을 반복해요
- 추가 공간
- O(1) · 구간 합과 최댓값만 저장해요
주의할 점
- 모든 합이 음수일 수 있어요. 최댓값을 0이 아니라 첫 구간의 합으로 시작해요.
- 여기서는 창의 크기가 고정이에요. 조건에 따라 크기를 바꾸는 윈도우는 포인터 이동 규칙이 달라져요.