확률

5. 확률적 분석과 랜덤화된 알고리즘 통계에 관한 기초 용어 설명 확률함수 어떤 사건 X가 일어날 확률을 Pr(X)라고 표현한다. 주사위를 던져서 1이 나오는 사건을 A, 짝수가 나오는 사건을 B라 하면 $$ Pr(A) = \frac16 , \ \ Pr(B) = \frac12 $$ 라고 표현할 수 있다. 기댓값 각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값이다. 예를 들어 500원 동전을 던져서 앞면이 나오면 500원을 얻는다고 해보자. 앞면이 나올 확률 X는 2분의 1, 즉 50%이다. 따라서 ...

5. 확률적 분석과 랜덤화된 알고리즘 5.1 고용 문제 직업 소개소에서 면접자를 추천 받으려면 적은 소개료를 지불해야 한다. 소개받아 면담한 후 일을 잘할 수 있는 사람이면 해고하고 새로운 지원자를 고용하면 된다. 고용하면 많은 소개료를 지불해야 한다. 이 떄 비용을 알고자 한다. Hire-ASSISTANT(n) 1 2 3 4 5 6 best = 0 // 0번은 가장 낮은 점수를 갖는 가상의 지원자 for i = 1 to n 지원자 i를 면접한다. if 지원자 i가 지원자 best보다 나은가? best = i 지원자 i를 고용한다. 위 의사코드가 비용을 의미한다. ...