점진적으로 평균 구하기

다음과 같이 집합 V에 n개의 숫자가 있는 경우,

avg_set

평균은 아래와 같이 구한다.

avg_general
하지만 집합의 원소를 한번에 하나씩만 얻어야 하는 경우 위의 공식으로 평균을 구하려면 반복문을 2개를 사용해야 한다. 하나의 반복문을 써서, 평균을 점진적으로 구하고자 한다면 아래의 공식을 사용한다.

avg_inc

 

과거에 평균을 점진적으로 구해야 하는 상황이 있었던 적은 없었다. 다만 그냥 끄적여 본 글이었다. 하지만

2년 후…

어떤 글로벌 기업에 코딩 테스트를 치뤘던 적이 있다. 문제 난이도는 soso였는데, 마지막 문제가 사용자가 1억명이 있는데, 각 사용자별 아이템 소모의 평균 값을 구하는 문제였다. 그렇게 제출했더라면 코딩 테스트를 탈락했을거다.

다행히도 이 글이 생각이 나서 점진적으로 평균을 구하도록 알고리즘을 수정했다. 함정은 1억명 유저의 각 평균을 효율적으로(어느정도 정확하다면) 구하는 것이었다.

 

Leave a Reply

Your email address will not be published. Required fields are marked *