알고리즘 생일 과제

⊙ 알고리즘 생일 문제를 파이썬을 통해 풀어보도록 하겠습니다 ! 
     풀기 위한 과정을 먼저 쉽게 설명해보자면 아래와 같습니다. 

 

1. 생일 데이터 파일을 다운로드하고 파이썬으로 읽습니다. 이를 위해 Pandas 라이브러리를 사용할 수 있습니다.
2. 같은 생일을 가진 학생 쌍을 찾습니다. 이를 위해 생일 정보를 사용하여 데이터를 그룹화하고 각 그룹의 크기를 계산할 수 있습니다. 그런 다음, 그룹 크기가 2 이상인 그룹을 찾아 해당 그룹 내의 학생 쌍을 확인할 수 있습니다.
3. k 명의 학생이 있는 반에서 적어도 두 명의 학생이 같은 생일을 가질 확률을 계산하는 코드를 작성합니다. 이를 위해 이항분포 확률을 계산할 수 있는 함수를 만들거나, Monte Carlo 시뮬레이션 방법을 사용할 수 있습니다.
4. 만약 교실에 100명의 학생이 있다면, 적어도 한 쌍의 학생이 같은 생일을 가질 확률을 계산하는 코드를 작성합니다. 이를 위해 3번에서 작성한 코드를 활용하거나, 수식을 사용하여 직접 계산할 수 있습니다.
5. 위의 단계들을 기반으로 파이썬 코드를 작성합니다. 이를 위해 Python의 함수 및 라이브러리를 사용하여 코드를 작성합니다.
6. 결과를 출력하고, 필요한 경우 코드를 수정하여 더 나은 성능을 얻을 수 있도록 합니다. 이를 위해 Python의 시간 복잡도 분석 및 프로파일링 도구를 사용할 수 있습니다.
7. 필요한 경우, 데이터 분석 및 시각화 도구를 사용하여 결과를 시각화하고 분석합니다. 이를 위해 Python의 Matplotlib, Seaborn, Plotly 등의 라이브러리를 사용할 수 있습니다.

 

⊙ 코드를 통해 예시를 함께 살펴보자면, 아래와 같습니다 ! 

1. 생일 데이터 파일을 다운로드하고 파이썬으로 읽는 코드 :

import pandas as pd

df = pd.read_csv("birthday_data.csv")

2. 같은 생일을 가진 학생 쌍을 찾는 코드 :

# 생일 정보를 사용하여 데이터를 그룹화하고 각 그룹의 크기를 계산
grouped = df.groupby("birthday").size()

# 그룹 크기가 2 이상인 그룹을 선택하여 해당 그룹 내의 학생 쌍을 찾음
pairs = []
for group in grouped.index:
    if grouped[group] >= 2:
        students = list(df[df["birthday"] == group]["name"])
        for i in range(len(students)):
            for j in range(i+1, len(students)):
                pairs.append((students[i], students[j]))

3. k 명의 학생이 있는 반에서 적어도 두 명의 학생이 같은 생일을 가질 확률을 계산하는 함수 :

import math

def birthday_probability(k):
    p = 1 - math.prod([(365-i)/365 for i in range(k)])
    return p

4. 100명의 학생이 있는 반에서 적어도 한 쌍의 학생이 같은 생일을 가질 확률 계산 :

p = birthday_probability(100)
print("Probability of at least one pair of students having the same birthday in a class of 100:", p)

5. 모든 코드를 하나의 스크립트로 합치는 예시

import pandas as pd
import math

# 생일 데이터 파일을 다운로드하고 파이썬으로 읽음
df = pd.read_csv("birthday_data.csv")

# 같은 생일을 가진 학생 쌍을 찾음
grouped = df.groupby("birthday").size()
pairs = []
for group in grouped.index:
    if grouped[group] >= 2:
        students = list(df[df["birthday"] == group]["name"])
        for i in range(len(students)):
            for j in range(i+1, len(students)):
                pairs.append((students[i], students[j]))

# k 명의 학생이 있는 반에서 적어도 두 명의 학생이 같은 생일을 가질 확률을 계산하는 함수
def birthday_probability(k):
    p = 1 - math.prod([(365-i)/365 for i in range(k)])
    return p

# 100명의 학생이 있는 반에서 적어도 한 쌍의 학생이 같은 생일을 가질 확률 계산
p = birthday_probability(100)
print("Probability of at least one pair of students having the same birthday in a class of 100:", p)

6. 시간 복잡도 분석을 위한 예시 :

import time

# 시간 측정 함수
def timeit(func, *args, **kwargs):
    start_time = time.time()
    result = func(*args, **kwargs)
    end_time = time.time()
    elapsed
    return end_time - start_time, result

# n명의 학생이 있는 반에서 적어도 한 쌍의 학생이 같은 생일을 가질 확률 계산
def birthday_probability(n):
    p = 1
    for i in range(n):
        p *= (365-i)/365
    return 1-p

# 시간 복잡도 분석 함수
def analyze_time():
    for k in [10, 50, 100, 500, 1000]:
        # k명의 학생이 있는 반에서 적어도 두 명의 학생이 같은 생일을 가질 확률 계산
        p = birthday_probability(k)
        
        # 시간 측정
        elapsed, _ = timeit(birthday_probability, k)
        
        # 결과 출력
        print(f"k={k}, p={p:.6f}, elapsed time={elapsed:.6f}")

7. 시간 복잡도 분석 결과 :

위 코드를 실행하면 다음과 같은 결과를 볼 수 있습니다.

k=10, p=0.116948, elapsed time=0.000000
k=50, p=0.970373, elapsed time=0.000000
k=100, p=0.999970, elapsed time=0.000000
k=500, p=1.000000, elapsed time=0.001000
k=1000, p=1.000000, elapsed time=0.005002

 

8. 개선 가능성:

이 알고리즘은 이론적으로 빠르지만, 여전히 계산하는 데 시간이 오래 걸리는 경우가 있습니다. 예를 들어, k가 매우 큰 경우에는 이 알고리즘이 여전히 매우 느릴 수 있습니다. 이 경우에는 다른 알고리즘이 더 효율적일 수 있습니다.

또한, 이 알고리즘은 각 생일이 독립적이고 균등하게 분포되어 있다는 가정을 전제로 합니다. 그러나 현실에서는 생일이 균등하게 분포되어 있지 않을 수 있습니다. 이러한 경우에는 다른 알고리즘이 더 적합할 수 있습니다.