문제 분류 수업 진도 대회 채점현황 순위 질문게시판
게임
스도쿠 타이핑 리듬 타자게임 타이핑 테트리스 타이핑 인베이더 타이핑 지뢰찾기 8192 공룡게임 타이핑 플래피버드 랭킹
로그인

7020 : 이동 평균

•시간제한: 1.000 S •메모리제한: 256 MB •제출: 1 •통과: 1 •만든사람: suakii

7020 : 이동 평균

시간 1.000s · 메모리 256MB · 제출 1 · 정답 1

문제 설명

$N$개의 정수로 이루어진 리스트가 주어집니다. 이 리스트에서 크기가 $K$인 윈도우를 한 칸씩 오른쪽으로 이동시키며 윈도우 내 원소들의 평균값을 구하는 것을 이동 평균(Moving Average)이라고 합니다.
예를 들어, 리스트가 [1, 2, 3, 4, 5] 이고 $K = 3$ 이라면 다음과 같이 $3$개의 이동 평균을 구할 수 있습니다.
1. [1, 2, 3]의 평균 = $2.00$
2. [2, 3, 4]의 평균 = $3.00$
3. [3, 4, 5]의 평균 = $4.00$
이동 평균은 주로 주식 시장이나 신호 처리 분야에서 데이터의 노이즈를 줄이고 추세를 파악하기 위해 널리 사용됩니다.
리스트와 $K$가 주어졌을 때, 모든 이동 평균을 계산하여 출력하는 프로그램을 작성하십시오.

[제약 조건]
• 리스트 크기 $N$, 윈도우 크기 $K$: $1 \le K \le N \le 10{,}000$
• 각 정수 원소: $-10^6 \le a_i \le 10^6$

입력 설명

첫째 줄에 리스트의 크기 $N$과 윈도우의 크기 $K$가 공백으로 구분되어 주어집니다. ($1 \le K \le N \le 10000$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 $-10^6$ 이상 $10^6$ 이하입니다.

출력 설명

구해진 $N - K + 1$개의 이동 평균을 계산된 순서대로 각 줄에 하나씩 소수점 둘째 자리까지 반올림하여 출력합니다.

입력 예시
COPY
복사되었습니다!

5 3
1 2 3 4 5

출력 예시
COPY
복사되었습니다!

2.00
3.00
4.00

도움

매번 크기 $K$만큼의 합을 구하면 시간 제한을 초과할 수 있습니다. 슬라이딩 윈도우 기법을 활용하여, 이전 윈도우의 합에서 가장 왼쪽 원소를 빼고 새로운 오른쪽 원소를 더하는 방식으로 누적 합을 갱신하면 $O(N)$의 시간 복잡도로 빠르게 해결할 수 있습니다.

출처/분류

NOTICE  —  BFStudy OJ 정보샘
애들아, 문제 많이 풀고 게임 잠깐 하는거지?
— 정보샘