안녕하세요~
문제에 대해 5분간 매직아이를 하게 되면
이 문제는 쉽다. 덤벼라 ! 와...
이건 어렵다. 제껴라 ! 를.. 어느 정도 느끼게 된 평민입니다. ㅋ
요새 한창 풀고 있는 주제가 있는데 막힌 부분이 있어서요.
여기 계신 분들이 알고리즘과 수학을 잘 아시니 왠지 딱 보면 아실거 같기도 해서 질문 드려요
문제는 이렇습니다.
입력은 12비트를 이용하는 양수. 0~4095 가 랜덤하게 무지 많이 들어옵니다.
그냥 계산할 수 없는 개수 천만. 백만 이라고 하죠.
출력은 매 단계마다의 평균과 분산을 내야 합니다.
천만개 백만개의 평균, 분산을 일일이 계산할 수는 없으니
제약조건으로 최대 k 개의 데이터만 본다.가 있습니다.
예를 들어 입력이
1 2 3 4 5 6 7 8 9 10
k 가 5 라고 한다면,
데이터 8 을 볼 때는 8 부터 이전 다섯개, 4 5 6 7 8 만 가지고 평균과 분산을 내는 식입니다.
데이터 9 를 볼 때는 9 부터 이전 다섯개, 5 6 7 8 9 가 되구요
평균은 합에서 하나 빼고 더하고 해서 매 스텝마다 거의 O(1) 에 구할 수 있는데,
문제는 분산입니다. 표준편차를 구할 수 있어도 되겠지요.
매 스텝마다 k 개를 다시 돌면서 평균과 빼고 제곱하고, 다시 더하고 하기에는 충분히 k 가 클 수 있습니다.
가장 이상적인건... 평균처럼 한 스텝에 들어올 데이터 나가는 데이터만 딱 보고 구하는겁니다 - ㅁ-;;
오차의 허용수준은 보통 문제에서 나오는 10^(-7) 보다 훨씬 관대하다고 할 때.. (10^(-3) 정도 ? ㅋ)
좋은 해결방법이 있을까요~?
룡이
안녕하세요~
문제에 대해 5분간 매직아이를 하게 되면
이 문제는 쉽다. 덤벼라 ! 와...
이건 어렵다. 제껴라 ! 를.. 어느 정도 느끼게 된 평민입니다. ㅋ
요새 한창 풀고 있는 주제가 있는데 막힌 부분이 있어서요.
여기 계신 분들이 알고리즘과 수학을 잘 아시니 왠지 딱 보면 아실거 같기도 해서 질문 드려요
문제는 이렇습니다.
입력은 12비트를 이용하는 양수. 0~4095 가 랜덤하게 무지 많이 들어옵니다.
그냥 계산할 수 없는 개수 천만. 백만 이라고 하죠.
출력은 매 단계마다의 평균과 분산을 내야 합니다.
천만개 백만개의 평균, 분산을 일일이 계산할 수는 없으니
제약조건으로 최대 k 개의 데이터만 본다.가 있습니다.
예를 들어 입력이
1 2 3 4 5 6 7 8 9 10
k 가 5 라고 한다면,
데이터 8 을 볼 때는 8 부터 이전 다섯개, 4 5 6 7 8 만 가지고 평균과 분산을 내는 식입니다.
데이터 9 를 볼 때는 9 부터 이전 다섯개, 5 6 7 8 9 가 되구요
평균은 합에서 하나 빼고 더하고 해서 매 스텝마다 거의 O(1) 에 구할 수 있는데,
문제는 분산입니다. 표준편차를 구할 수 있어도 되겠지요.
매 스텝마다 k 개를 다시 돌면서 평균과 빼고 제곱하고, 다시 더하고 하기에는 충분히 k 가 클 수 있습니다.
가장 이상적인건... 평균처럼 한 스텝에 들어올 데이터 나가는 데이터만 딱 보고 구하는겁니다 - ㅁ-;;
오차의 허용수준은 보통 문제에서 나오는 10^(-7) 보다 훨씬 관대하다고 할 때.. (10^(-3) 정도 ? ㅋ)
좋은 해결방법이 있을까요~?
15년 전