Problem Set 1

• All your assignments should be uploaded on your blog. In LMS, leave your address. 
• You should use Korean.
• Due date: Next Tuesday 12:00
• No late submissions will be accepted except official excuses.

 

1. Download the birthday data. 
2. Manually determine the pairs of you who have the same birthday. Explain your method of solution.(생일이 같은 쌍을 수동으로 결정한다. 해결방법을 설명해라)
3. Develop an algorithm for the first question using pseudo code.
4. Create code that calculates the probability of having at least two students with the same birthday in a class of k students. Apply several different ks. (K명의 학급에 생일이 같은 학생이 2명 이상 있을 확률을 계산하는 코드를 작성해라. 여러 다른 K를 적용해라)
5. Demonstrate that if there are 100 students in a classroom, it is 99.999% probable that there is a pair of students with the same birthday. Conduct computational experiments to solve this problem. 
6. Apply any resources available to improve your answers and compare your original solution with others. Explain which resources you used and how you employed them.

 

• Please do not post the birthday data on your blog to avoid violating privacy concerns. 
• If you want an argument, please refer to the following video: 

            https://youtu.be/LZ5Wergp_PA

 

 

 

 

 

<Birthday Problem>

- 생일역설 또는 생일문제로 알려진 문제

 

 

<생일이 같은 쌍을 수동으로 결정하고 해결방법을 설명>

1) 생일 데이터들을 월별로 나눈다.(ex: 1월 몇명, 2월 몇명, 3월 몇명, ..., 12월 몇명)

2) 달 안에서 초(1~10), 중(11~20), 말(21~30)으로 나눈다.

3) 하나하나 직접 비교한다.

 

생일이 똑같은 사람이 한 쌍 이상 존재하기 위해서는 몇 명이 필요할까? 많은 사람이 모여야 생일이 같은 한 쌍이 나올 것 같지만, 23명의 사람만 모여도 생일이 같은 한 쌍이 나올 확률이 50%가 넘어가고, 57명의 사람이 모이면 생일이 같은 한 쌍이 나올 확률이 99%가 넘어간다. 

이러한 생일 역설 문제는 일반적인 확률에 대한 인간의 직관이 다른 결과를 보이는 대표적인 문제이다.

수학적으로 확률 계산을 해보면 쉽게 납득할 수 있다. 어떤 사건이 일어날 확률을 p라고 했을 때 그 사건이 일어나지 않을 확률은 1-p이다.(여사건) 

만약 366명 이상의 사람이 있다면 '비둘기집 원리'에 따라 생일이 같은 두 사람이 존재해야 한다. 365명 이하의 사람이 있을 경우를 계산한다. n명의 사람이 있을 때 그 중 생일이 같은 사람이 둘 이상 있을 확률을 p(n)이라고 한다면, 반대로 모든 사람의 생일이 다를 확률은 1-p(n)이 된다. 

 

 

 

birthday라는 함수를 만들어서 k명 그룹에서 생일이 동일한 사람이 있을 확률을 계산한다. 파이썬으로 풀어보았다.

k = 총 사람수

==> 23명이상이되면 50%가 넘어간다.

==> 100명일 땐 99.99%

 

 

 

 

또한 이렇게 풀이하다가 다른 생각도 났다. 만약 C++로 풀게 된다면 먼저 엑셀에 있는 생일정보를 파일읽기로 읽은 후  Sort 함수를 이용한다. 이렇게 정렬시킨 후 정렬된 값들을 한 번에 두 개씩 비교하며 같은 생일이 존재하는지 확인한다. 

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

    int cnt = 0;
    int n, birthday, find;
    double p;

    vector <int> v;
    vector <int> pair;

    ifstream fp("Birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "파일이 존재하지 않습니다." << endl;
    }

    sort(v.begin(), v.end());

    for (int i = 1; i < n; i++) {

        if (v[i - 1] == v[i]) {
            cnt += 1;
            pair.push_back(v[i - 1]);
        }

    }

    p = 1 - pow((364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 똑같은 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 똑같은 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 똑같은 생일을 가진 쌍의 개수: " << cnt << endl;
        for (int i = 0; i < pair.size(); i++) {
            cout << pair[i] << endl;
        }
    }

    fp.close();

}

 

 

 

 

 

 

 

 

 

 

 

*참고 사이트: https://dad-rock.tistory.com/779

                      https://m.blog.naver.com/alwaysneoi/220261751961