Loopin's Page

1. 문제 개요

- (생일 문제) n 명의 사람들로 구성되어 있는 모임에서 적어도 두 사람의 생일이 같을 확률은 얼마인지 구한다. (윤년은 고려하지 않으며 모임 구성원들의 생일에 대한 모든 가능한 조합들은 가능성이 동일한 것으로 생각한다.)

- 이 문제의 식을 유도하는 과정을 Python 언어로 구현한다.

- Python 은 2.6.2 버전으로 적용되었다.

2. 문제 분석(알고리즘 및 해결방안)

①  여사건의 개념으로 접근한다.

②  전체 n 명의 사람들로 구성되어 있는 모임에서의 모든 생일의 수가 전체가 되고, 문제에서 주어진 조건의 여집합에 해당하는 것은 n 명의 사람들 모두가 생일이 일치하지 않을 경우이다. 곧, 전자가 분모에, 후자가 분자에 해당한다.

③  단, 주의해야 할 점은 서로 다른 생일들을 선택할 때 순서의 의미가 있다는 점이다. 전체의 경우가 총 선택 수에 대해 중복을 허용하는 순열이므로 여사건에 해당하는 부분에 순서를 배치해야 함을 누락해선 안 된다.

④  유도한 식을 프로그래밍 화하여 답을 구한다.

3. 결과(소스 및 스크린샷)

풀이는 다음과 같다.

①  전체 사건은 중복을 허용한 365일 중 n만큼을 골라야 한다. => 365^n

②  여사건은 총 1년 365일에서 중복되지 않는 한도로 n만큼을 골라야 하므로(곧, n 은 반드시 365 이하여야한다.) 365Cn 지만, 전체 사건에서 n만큼 선택에 있어 순서가 의미가 있으므로 여사건 또한 순서 의미를 지니게 된다. 곧, 일자로 나열하는 경우의 수가 포함되어야 한다. => 365Cn*n!

③  최종 구하고자 하는 사건으로 정리하면, => 1 - (365Cn*n!)/365^n 가 구하고자 하는 사건의 확률이다.

④  코딩

def cbn(x,y):

 result = 1

 underresult = fact(y)

 while y > 0 :

  result = result * x

  y = y - 1

  x = x - 1

 return (result/underresult)

def fact(n):

 if n <= 1:

  return 1

 else:

  return n * fact(n-1)

def calcp(n):

 undernumber = 365 ** n

 undernumber = float(undernumber) / fact(n)

 return (1-(cbn(365,n)/undernumber))

## confirm the problem

a = 0

i = 1

while i < 100:

 a = calcp(i)

 print a, i

 i = i + 1

4. 고찰

①  실행화면 결과는 한 행마다 앞쪽은 해당 확률, 뒤쪽은 n 의 값이다. n 의 값이 증가할수록 확률은 급격히 증가하는 모습을 보인다. 365에 못 미치는 60 정도만 와도 이미 99/100 의 확률을 보임을 알 수 있다. 확률이 반이 되는 위치는 n = 23 일 때이며, 의미하는 바는 23명 이상이 있다면, 적어도 두 명 이상은 생일이 같은 경우가 50% 이상임을 말한다.

②  교수님께서 지적하신 부분의 실수를 저지르고 말았다. 결과가 계속 0 으로 나오기에 정수/정수의 결과를 떠올리기 전에 함수간 값 전달에 문제가 있었던 게 아닐까 한참 고민한 점이 많은 시간을 앗아갔다. 그 외에 제곱 연산에 ‘^’ 을 사용, 덧셈 값이 나와 오류를 겪기도 했다. 팩토리얼 연산은 수업 시간 때 배웠었던 재귀적 호출법을 이용하여 구현하였고, 나머진 미리 언급된 알고리즘에 따라 구현되었다.