기초 개념
슬라이딩 윈도우
창문을 밀면서 보기
열흘 동안의 기온입니다. 연속한 3일의 합이 가장 큰 때를 찾습니다.
창을 오른쪽으로 한 칸씩 밉니다. 밀기 전에 합이 오를지 내릴지 고르세요.
30
51
22
83
64
95
16
47
78
29
나갈 칸들어올 칸
처음 세 칸의 합 3 + 5 + 2 = 10
지금까지 가장 큰 합 10 · 맞힌 횟수 0/0
일곱 번 중 0번 맞혔습니다. 밀 때마다 한 계산은 빼기 하나, 더하기 하나였습니다.
10 → 15 → 16 → 23 → 16 → 14 → 12 → 13창을 한 칸씩 밀 때마다 합이 이렇게 이어졌습니다. 가장 큰 합은 23.
- 한 칸 밀면 — 바뀌는 칸은 둘뿐이다. 나가는 칸과 들어오는 칸
- 그래서 — 세 칸을 다시 더하지 않고
− 나간 값+ 들어온 값만 한다
창을 한 칸씩 밀며 합을 이어 가는 방법 = 슬라이딩 윈도우
창마다 다시 더하기 · 100,000칸900,010,000번
한 칸 밀며 이어 가기 · 100,000칸190,000번
연속한 칸이고, 창 크기가 정해져 있어야 한다
- 연속한 칸 — 건너뛴 칸이 끼면 한 칸 밀어서 합을 이을 수 없다
- 정해진 크기 — 이 장은 창 크기 k 가 처음부터 끝까지 같다. 창이 늘었다 줄었다 하는 문제도 같은 틀이지만 여기서는 다루지 않는다
- 그래서 — 매번 달라지는 나가는 값과 들어오는 값만 계산하면 된다
코드는 처음 한 번만 다 더한다
① 과 같은 열 칸, 창 3. 다음을 눌러 빠지는 값과 들어오는 값을 보세요.
30
51
22
83
64
95
16
47
78
29
다음을 눌러 한 줄씩 넘겨 보세요
n = 10
max_window_sum.py
- 1def max_window_sum(arr, k):
- 2 n = len(arr)
- 3 window = sum(arr[:k])
- 4 best = window
- 5 for i in range(k, n):
- 6 window += arr[i] - arr[i - k]
- 7 best = max(best, window)
- 8 return best
0 / 26
window = sum(arr[:k])— 처음 창만 직접 더한다window += arr[i] - arr[i - k]— 들어오는 칸을 더하고 나가는 칸을 뺀다best— 지금까지 본 합 중 가장 큰 것
칸이 10개이고 창 크기가 4이면, 창은 몇 곳에 놓일까요?
처음 창과 끝 창에서 틀린다
window = sum(arr[:k])— 이 줄을 빼먹으면window가 없는 채로+=를 해서 에러가 난다arr[i - k + 1]— 나갈 칸 대신 아직 창 안에 있는 칸을 뺀다. 에러 없이 합만 틀린다k > n— 에러가 나지 않고 전체를 더한 값이 돌아온다. 먼저 k 가 칸 수 이하인지 확인한다
문제에서 이 말이 보이면
연속한 구간길이가 k 로 정해져 있다최대·최소 구간 합
다음 장에서는 어떤 구간이든 뺄셈 한 번으로 합을 구하는 누적합을 봅니다.