2023 spring Algorithm
week01 homework
Problem Set 1
생일이 같은 짝(pair) 찾기
우리 수업의 수강생 100명 중 생일이 같은 pair를 찾는 방법은 다음과 같다.
모든 학생에게 임의의 번호(1부터 100까지)를 부여한다.
1번 학생의 생일과 2번 학생의 생일을 비교한다.
1번 학생의 생일과 3번 학생의 생일을 비교한다.
...
1번 학생의 생일과 100번 학생의 생일을 비교한다.
2번 학생의 생일과 3번 학생의 생일을 비교한다.
...
2번 학생의 생일과 100번 학생의 생일을 비교한다.
...
99번 학생의 생일과 100번 학생의 생일을 비교한다.
이를 psudo code 로 나타내면 다음과 같다.
for i in range 99:
for j in range(i+1, 100):
if (student[i] == student[j]):
print("생일이 같은 학생은", i,"학생과", j, "학생입니다.")이를 실제 python 코드로 작성 하면 다음과 같다.
(학생의 개인정보 보호를 위해 이름대신 index를 사용했다. )
(실제 데이터에는 생일을 입력하지 않은 학생이 있지만, 생일을 입력하지 않은 학생은 없다고 생각한다. )
100여명의 학생이 있을 때, 생일이 같은 사람이 있을 확률이 99.99% 임을 증명
그 일이 일어날 확률 + 일이 일어나지 않을 확률 = 1 을 이용한다.
따라서 생일이 같은 사람이 없을 확률 을 먼저 구하면 생일이 같은 사람이 있을 확률을 알 수 있다.
n명의 학생 중 학생 a, b (r명)를 선택하는 공식은 다음과 같다.
n은 10이고 r은 2일때, 45개의 pair가 생성된다.
n은 15이고 r은 2일때, 105개의 pair가 생성된다.
n은 20이고 r은 2일때, 190개의 pair가 생성된다.
...
n은 100이고 r은 2일때, 4950개의 pair가 생성된다.
1년은 365일이므로(2월 29일 제외) 이렇게 선정한 학생 pair가 모두 생일이 같지 않은 pair들일 확률은 0에 수렴한다.
따라서 100여명의 학생이 있을 때, 생일이 같은 사람이 있을 확률이 99.99% 이다.
또 다른 방식으로 해결할 수 있는데, 생일이 같지 않을 확률을 다른 방식으로 구할 수 있다.
k명의 학생이 있다고 생각했을 때, 모두 생일이 같지 않을 확률을 구해보자.
학생 1의 생일이 m월 d일이라고 했을 때 학생1과 학생 2는 생일이 다르다.
학생 3의 생일은 학생 1과 학생 2의 생일이 될 수 없고,
학생 4의 생일은 학생 1과 학생 2와 학생 3의 생일이 될 수 없고,
...
학생 k의 생일은 학생 1과, ..., 학생 k-1 의 생일이 될 수 없다.
이것을 식으로 나타내면 다음과 같다.
{(365-1) / 365} * {(365-2) / 365} * {(365-3) / 365} * ... * {(365-k+1) / 365} k가 100일 때 위의 값(100명의 학생이 모두 생일이 같지 않을 확률)은 0에 수렴하는 수이다.
따라서 100여명의 학생이 있을 때, 생일이 같은 사람이 있을 확률은 99.99% 이다.
__
컴퓨터공학과 이가인
