C++로 구현하는 숫자 스트림의 실시간 평균 계산

숫자들의 평균(Average)은 모든 숫자의 합을 숫자의 개수로 나눈 값입니다.

이 문제에서는 숫자 스트림(stream)이 주어지며, 숫자가 하나씩 추가될 때마다 그 시점까지의 평균을 출력해야 합니다.

동작 방식 예시

다음과 같이 5개의 숫자로 이루어진 스트림이 있다고 가정해 보겠습니다.

24 , 76 , 29 , 63 , 88

각 시점에서의 평균은 다음과 같습니다.

24 , 50 , 43 , 48 , 56

즉, 숫자가 스트림에 추가될 때마다 해당 시점까지의 평균을 구해야 하므로, 1개일 때, 2개일 때, 3개일 때... 의 평균을 순차적으로 계산하게 됩니다. 이때 이전에 구한 평균 값을 활용하면 효율적으로 계산할 수 있습니다.

알고리즘

매번 모든 숫자를 다시 더하는 대신, 직전 평균과 새로 들어온 숫자만으로 현재 평균을 갱신하는 것이 핵심입니다.

Step 1 : i를 0부터 n(스트림 길이)까지 반복합니다.
Step 2 : 아래 공식으로 평균을 갱신합니다.
         Average = ((Average × i) + arr[i]) / (i + 1)
Step 3 : 평균을 출력합니다.

여기서 i는 지금까지 처리한 숫자의 개수이며, Average × i는 기존 숫자들의 합에 해당합니다. 여기에 새로운 숫자 arr[i]를 더하고 전체 개수 (i + 1)로 나누면 새로운 평균이 됩니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int main(){
    int arr[] = { 24 , 76 , 29, 63 , 88 };
    int average = 0;
    int n = sizeof(arr) / sizeof(arr[0]);
    for(int i = 0 ; i < n ; i++){
        average = ((average * i) + arr[i]) / (i+1);
        cout<<"스트림의 첫 "<<i+1<<"개 숫자의 평균: "<<average<<endl;
    }
    return 0;
}

실행 결과

스트림의 첫 1개 숫자의 평균: 24
스트림의 첫 2개 숫자의 평균: 50
스트림의 첫 3개 숫자의 평균: 43
스트림의 첫 4개 숫자의 평균: 48
스트림의 첫 5개 숫자의 평균: 56

참고 사항

위 알고리즘은 정수형뿐 아니라 float, double 등 모든 데이터 타입에 동일하게 적용할 수 있습니다. 다만 정수형 나눗셈에서는 소수점 이하가 잘리므로, 정확한 소수 평균이 필요하다면 double 타입을 사용하는 것이 좋습니다. 이 방식은 매번 전체 합을 다시 계산하지 않고 이전 평균을 재활용하기 때문에 O(n)의 시간 복잡도로 스트림의 각 시점별 평균을 효율적으로 구할 수 있습니다.