7020 : 이동 평균
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 리스트가 주어집니다. 이 리스트에서 크기가 $K$인 윈도우를 한 칸씩 오른쪽으로 이동시키며 윈도우 내 원소들의 평균값을 구하는 것을 이동 평균(Moving Average)이라고 합니다.
예를 들어, 리스트가
1.
2.
3.
이동 평균은 주로 주식 시장이나 신호 처리 분야에서 데이터의 노이즈를 줄이고 추세를 파악하기 위해 널리 사용됩니다.
리스트와 $K$가 주어졌을 때, 모든 이동 평균을 계산하여 출력하는 프로그램을 작성하십시오.
[제약 조건]
• 리스트 크기 $N$, 윈도우 크기 $K$: $1 \le K \le N \le 10{,}000$
• 각 정수 원소: $-10^6 \le a_i \le 10^6$
예를 들어, 리스트가
[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$개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 $-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)$의 시간 복잡도로 빠르게 해결할 수 있습니다.