연속 구간을 한 칸씩 옮기며 이전 계산을 재사용하는 패턴
고정 또는 가변 길이의 연속 구간을 모두 검사할 때 매 구간을 처음부터 계산하지 않기 위해 씁니다. 새 값은 넣고 오래된 값은 빼며 O(n²)을 O(n)으로 줄일 수 있습니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
화요일이 되면 지난주 월요일 기록은 빼고 이번 월요일 기록만 더해 새 평균을 냅니다.
지금으로부터 10초 안의 움직임만 보고 싶다면 오래된 장면은 버리고 새 장면을 계속 넣습니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
최근 5분 요청량·오류율·최댓값을 계속 갱신합니다.
연속 구간의 평균과 현재 값의 차이를 비교합니다.
조건을 만족하는 최소 길이 부분 문자열을 찾습니다.
최근 짧은 시간에 반복된 결제 횟수와 금액을 계속 확인합니다.
최근 N개 음성 샘플의 평균 크기를 갱신해 잡음을 감지합니다.
왼쪽과 오른쪽 경계가 배열 위를 한 방향으로 이동합니다. 단순 합은 뺄 값과 더할 값만 갱신하고, 최댓값은 값이 감소하는 deque를 유지해 각 원소가 한 번씩 들어오고 나가게 합니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 고정 구간 합 | add right, remove left | O(n) |
| 가변 창 | two pointers | O(n) |
| 구간 최댓값 | monotonic deque | O(n) |
| 매번 max | max(window) | O(nk) |
deque=[1]작은 1 제거 → deque=[3]deque=[3,2], 첫 창 최댓값 33,2 제거 → deque=[5], 다음 최댓값 5설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기