The Hiring Problem

이전 모든 면접자들의 점수보다 높으면 합격시키는 문제

• 논리적 오류

  • 점수가 오름차순으로 정렬되어 있으면 모두 다 뽑힘 (반대)
  • 0번 구직자는 항상 합격

• 해결책

  → 지원자들의 순서를 무작위로 재배치 - Randomize!

비용분석

• 1명 면접 비용 $c_j$, 1명 고용 비용 $c_h$

• $n$명의 구직자 중 $m$명을 뽑았을 때 드는 비용 = $c_jn + c_hm$

• 위의 변수 중 $m$만 바뀔 수 있는 수. 고용자의 평균 수($E[m]$) 계산 필요

• $i$ 번째 지원자가 뽑힐 확률 = $p_i$ X_i (확률변수) 는 0 또는 1 을 가지는 값이므로 0 or 1

  $\begin{cases} 0 \text{ \;Candidate i is not hired}\\ 1 \text{ \; Candidate i is hired}\\ \end{cases}$

  $\therefore m = X_1 + X_2 + X_3 + \cdots +X_n$

  $\therefore E[m] = E[X_1 + X_2 + X_3 \cdots + X_n] = E[X_1] + E[X_2] + \cdots + E[X_n]$

• $E[X_i] = 1 \times p_i + 0 \times (1-p_i) = p_i$

  $\therefore E[m] = p_1 + p_2 + \cdots + p_n$

• $i$번째 구직자가 뽑힐 확률 $p_i = i$명 중 가장 뛰어날 확률 = $\frac{1}{i}$

  $\therefore E[m] = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \approx O(logn)$

난수 만들기

$Random(a, b) = a, a+1, \cdots, b$ 중 어느 하나를 같은 확률로 반환하는 함수

• C/C++ 에서는 rand 함수를 사용할 경우, 같은 결과 반복

  → '시간'을 인수로 넣어 항상 다르게 콜백 (마우스위치, 메모리 사이즈 등을 쓰기도 함)

  #quiz Random(0,1) 함수만을 가지고 Random(0, n-1)(단, n은 3이상의 양수) 를 구현해보시오.

  → random(0,3) 에서 한 가지에 대하여 다시 시도 (무한루프 가능)

  각각 나올 확률 = $\frac{1}{4}$ 가 등비인 등비급수의 합 = $\frac{1}{3}$

  수행시간

  Function Random(0, n-1){
  	while(1){
  		a = random(0,1)
  		b = random(0,1)
  		
  		if(a = 0 && b = 0) return 0;
  		else if(a = 0 && b = 1) return 1;
  		else if(a = 1 && b = 0) return 2;
  	}
  }
  

재배열 알고리즘(permute by Sorting)

• P[]의 난수 정렬 → P[]의 인덱스 순서를 바탕으로 A재배열