randomized (2) 썸네일형 리스트형 확률 가중 다수결 알고리즘 (Randomized Weighted Majority Algorithm) 지난 시간에 함께 공부한 문제는 다음과 같습니다. 여러분은 다음날 어떤 회사의 주식이 오를지 내릴지 관심이 있습니다.(등락의 폭은 상관하지 않습니다.) 아무 정보도 없이 무턱대고 예상을 하는 것은 너무 멍청하다고 생각한 여러분은 총 \(n\) 명의 전문가를 초빙합니다. 매일 각 전문가는 다음날 회사의 주식이 오를 것인지 내릴 것인지에 대해서 예측합니다. 전문가들도 예측에 실패할 수 있습니다. 여러분의 목표는 가장 적중률이 좋은 전문가에 필적하는 정도의 예측을 하는 것입니다. 다음은 지난 포스트에서 같이 알아본 내용을 간략히 정리한 것입니다. 만약 (누구인지는 모르지만) 전문가 집단 중 매번 예측을 맞추는 달인이 존재하면, \( \log_2 n \) 번 안에 해당 달인을 찾아낼 수 있습니다. 일반적인 경우.. 야오의 법칙 (Yao's Principle) 이번에는 Yao's principle에 대해서 알아보도록 하겠습니다. 이 글은 이전 포스트에서 이어지는 내용이 많으므로 이를 먼저 읽어 보시는 것을 추천드립니다. 또한 확률에 대한 기본적인 내용을 숙지하셨다는 가정 아래 글이 작성되었다는 점도 밝힙니다. 2019/08/11 - [수학적 도구/Randomness] - Arbitrary & Random Arbitrary & Random 이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데.. gazelle-and-cs.tistory.com 지난 시간 'random'을 설명하기 위해서 같이 고민했던.. 이전 1 다음
