Table of Contents
할 일
- 모든 과제는 블로그에 올리고 LMS에 링크 제출하기
- 교수님을 위해 한국어로 쓰기
- 다음주 화요일 12:00까지(수업은 목요일)
- 정당한 사유 없이 지각 제출 불가
- 만약 다른 학생과 토의했다면 그것도 모두 기록할 것. 과제를 위해 한 모든 활동을 기록하라.
- 생일 데이터 다운로드: 개인정보 보호 문제로 파일은 비공개, 무작위로 생성한 생일 사용 가능.
- 생일이 같은 두 사람의 쌍을 수동으로 결정한다. 해결 방법을 설명한다.
- 의사 코드를 사용하여 첫 번째 질문에 대한 알고리즘을 개발한다. (스타일 무관) (이 부분이 이해가 잘 안 돼서 생일 쌍을 찾는 알고리즘과 그게 존재할 확률을 계산하는 알고리즘 2개를 만들었다)
- k명의 학생으로 구성된 학급에 생일이 같은 학생이 2명 이상 있을 확률을 계산하는 코드를 작성한다. 여러 개의 다른 k를 적용한다.
- 한 교실에 학생이 100명일 경우 생일이 같은 학생 한 쌍이 있을 확률이 99.999%임을 증명한다. 이 문제를 해결하기 위해 계산 실험을 수행한다.
- 알고리즘을 구두 설명으로 단어로 설명한다.
- 코딩하기 전에 알고리즘의 정확성을 보이라. 귀납적 증명을 사용하라.
- 효율성을 보이라. 점근 표기법(시간복잡도)을 사용하고 그 이유를 설명한다.
- 설명을 위한 의사 코드를 작성한다.
- 문제를 해결하기 위한 코드를 개발한다.
- 결과를 표시한다.
- 답안을 개선하기 위해 사용 가능한 모든 리소스를 적용하고 원래 솔루션과 다른 솔루션을 비교한다. 어떤 리소스를 어떻게 사용했는지 설명한다.
- 개인 정보 보호를 위해 생일 데이터는 블로그에 업로드하지 말 것.
- 만약 99.999%라는 확률이 아직도 의심스럽다면 첨부한 동영상을 보라.
https://youtu.be/LZ5Wergp_PA
문제 설명
서로 다른 사람이 23명 있다. 이 중에 생일이 같은 두 사람의 쌍이 존재할 확률은 얼마나 될까? 서로 다른 사람이 100명 있을 때는? (편의상 윤년은 고려하지 않는다)
답은 각각 50% 이상, 99.999% 이상이다. 위키백과를 참고하여 간단히 풀이하자면, 우선 모든 사람의 생일이 모두 다를 확률을 구한 뒤 1에서 빼야 한다. 모든 사람의 생일이 다를 확률은 365일 중 사람 수만큼 비복원추출을 하는 것과 같다. 자세한 식은 위키백과에서 직접 확인하자.
문제 풀기
수작업 해결
* 사전에 조사된 수강생 생일 데이터를 엑셀 파일로 받아 이용했다. 수동으로 하라고는 했지만 도구를 사용하지 말라는 말은 없었으니까
- 엑셀로 파일을 열고, 생일을 기준으로 정렬한다.
- 스크롤을 내리면서 서로 같은 두 날짜가 쓰인 행을 찾는다.
- 서로 같은 생일의 쌍만 남기고 나머지 행은 지운다.
- 완성
알고리즘 구상: 생일 쌍 찾기
사람이 답을 찾을 때는 보통 시각에 의존하니 보기 좋으라고 정렬했지만, 프로그램은 그럴 필요가 없다. 정렬보다 해시 테이블이 빠르다.
생일을 키로, 이름(또는 개인을 구분할 수 있는 정보)을 값으로 갖는 빈 해시 테이블을 준비해둔다. 생일 데이터를 차례로 읽어들이며 해시 테이블에 같은 생일이 있는지 확인하고 있다면 바로 반환하고, 없다면 해시 테이블에 추가한다. 생일 쌍을 찾아 반환하거나 모든 데이터를 확인할 때까지 반복한다. 생일 쌍이 없다면 None을 반환한다.
알고리즘 구상: 생일 쌍이 존재할 확률
나는 이번 과제가 잘 이해가 안 되는 게, (1) 주어진 생일 데이터 내에서 생일이 같은 쌍을 찾아내라는 건지, (2) 쌍이 존재할 확률을 구하라는 건지, (3) 무작위로 생일을 배치하고 쌍을 찾아내는 실험을 반복해 통계적 확률이 수학적 확률에 수렴하는지 확인하라는 건지 모르겠다.
(1) 수업시간에 알고리즘 다 배웠고 증명하는 것도 배웠으니 ‘직접 구상하라’고 하는 건 이상함
(2) 수학 계산만 하면 되니까 굳이 알고리즘이라고 할 게 없음
(3) 어차피 반복 실험을 할 거라면 생일 데이터는 매번 새로운 게 필요하니까 수강생의 생일 데이터를 수집한 의미가 없고, 반복이라는 요소가 추가되었을 뿐 (1)번과 알고리즘은 같음.
과제 마감 기한이 길지 않아 교수님께 문의 올리고 답변을 기다리기엔 틈틈이 글을 써야 해서 내가 생각하기에 이걸 요구하셨을 것 같다 싶은 것을 하기로 했다(메일을 보내 두기는 했다). 공지에 써있는 것도 ‘확률을 구하라’였고, 참고하라고 올려주신 영상도 저 문제를 확률적으로 증명하는 내용이었지만 그래서는 알고리즘을 검증하고 평가할 게 없으니 (1)번으로 쓰겠다.
- 필요한 것은 사람의 수
k. - 생일 문제의 공식에 따라 모든 사람의 생일이 다를 확률을 구한다.
- 그 값을 1에서 뺀다.
- 답을 반환한다.
실험과 증명
1. 알고리즘을 구두 설명으로 단어로 설명한다.
2. 코딩하기 전에 알고리즘의 정확성을 보이라. 귀납적 증명을 사용하라.
3. 효율성을 보이라. 점근 표기법(시간복잡도)을 사용하고 그 이유를 설명한다.
4. 설명을 위한 의사 코드를 작성한다.
5. 문제를 해결하기 위한 코드를 개발한다.
6. 결과를 표시한다.
알고리즘을 말로 설명한 것은 알고리즘 구상: 생일 쌍 찾기 문단에 있다.
귀납적 증명
* 내가 구상한 알고리즘이 입력의 크기에 상관 없이 올바르게 동작하는지 보이면 된다고 이해했음.
k = 0
사람이 없으면 읽을 데이터도 없고 생일도 없으므로 생일이 같은 쌍은 없다.k = 1
사람이 1명밖에 없으므로 생일이 같은 쌍은 찾을 수 없다.k = 2
첫 번째 사람의 데이터를 읽고, 이미 저장된 데이터가 없으므로(저장된 데이터 중 일치하는 생일이 없으므로) 해시 테이블에 저장한다.
두 번째 사람의 데이터를 읽고, 해시 테이블에 같은 데이터가 있는지 찾는다. 만약 있다면 함께 반환한다.
만약 없었다면 모든 사람의 데이터를 확인했으므로None을 반환한다.k > 2
3번과 같은 과정을 첫 번째 쌍을 찾을 때까지 반복하거나, 없다면 모든 데이터를 확인할 때까지 반복한다.
효율성 계산
이 알고리즘에서 수행해야 하는 과정은 다음과 같다. 입력의 크기는 n이다.
- 데이터 읽기
- 해시 테이블 확인하기
- 해시 테이블에 일치하는 데이터가 있을 경우: pair로 반환하기
- 없을 경우: 해시 테이블에 추가하고
continue하기
데이터를 읽는 과정과 해시 테이블을 확인하는 과정은 별다른 추가 과정을 필요로 하지 않으므로 매 실행마다 O(1)이다. 해시 테이블이 왜 O(1)인지에 대해서는 해시 테이블의 개념에 대해 공부하면 알 수 있다.
해시 테이블에 일치하는 데이터가 있는지 확인하여 반복을 더 할지 결정하는 과정은 입력의 크기에 따라 달라진다. 최선의 경우 2번만 하면 되므로 O(1)이고, 최악의 경우 모든 입력을 확인하므로 O(n)이다. 최선도 최악도 아닌 평균적인 경우는 어떻게 구해야 할지 모르겠다. 산술적인 평균이라 한다면 (1 + n) / 2이므로 O(n)이다.
효율성 계산: chatGPT 풀이
* 내가 받은 답변을 그대로 번역한 것이다.
코드의 시간 복잡도는 O(n)이며, 여기서 n은 데이터 집합의 행 수입니다. 이는 코드가 데이터 집합의 각 행을 정확히 한 번씩 반복하고 각 행에 대해 일정한 양의 작업을 수행하기 때문입니다.
for 루프는 _data에 있는 행의 인덱스를 반복하므로 정확히 n번 실행되며, 여기서 n은 _data에 있는 행의 수입니다. 루프 내에서 각 반복은 사전 테이블에 액세스하고 업데이트하는 일정한 양의 작업을 수행합니다.
따라서 코드의 전체 시간 복잡도는 입력 데이터의 크기에 따라 선형적인 O(n)입니다. 이는 생일 문제를 푸는 데 효율적인 시간 복잡도입니다.
의사 코드
- 빈 해시 테이블을 준비한다(C++
unordered_map, 파이썬dict등). 키는 생일이고 값은 생일인 사람의 이름(또는 개인을 구분할 수 있는 정보)이다. - 생일 데이터를 읽어들이며 아래 과정을 반복한다.
- 해시 테이블에 지금 읽어들인 사람의 생일이 이미 존재하는지 확인한다.
- 만약 존재한다면, 찾아낸 값과 함께 생일 쌍으로 반환한다.
- 그렇지 않다면 해시 테이블에 정보를 추가하고 다음 반복으로
continue한다.
- 모든 데이터를 읽어도 반환할 수 있는 쌍이 없었다면 답이 없는 것으로,
None(사용하는 언어에 따라null로 표현하기도 함)을 반환한다.
코드 작성
사용 언어: 파이썬
파이썬의 딕셔너리(dict, dictionary)는 해시 구조로 이루어져 있으므로(참고) 이 알고리즘에서 해시 테이블로 사용할 것이다.
이 글의 초입에도 쓰여 있지만 생일 데이터는 공개하지 않는다. 대신 아래에 랜덤한 생일 데이터를 생성하는 코드를 추가했으니 직접 해보고 싶다면 그쪽을 복사해서 실행해보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import pandas as pd
# 개인정보 보호를 위해 수강생의 이름을 지우고 번호 인덱스로 대체함
file_route = r'algorithm\homework\week01\Algorithms - Birthday Data edited.csv'
data = pd.read_csv(file_route, header=0, encoding='utf-8')
data.dropna(inplace=True) # 수강생 중 생일을 제공하지 않은 데이터는 제외
print(data.info())
def find_B_pair(_data):
table = {} # <class 'dict'>
for i in _data.index:
k = _data.iloc[i]
if k['Birthday'] in table:
return (table[k['Birthday']], k['Number'], k['Birthday'])
else:
table[k['Birthday']] = k['Number']
return None
for _ in range(0, 10): # 데이터를 무작위로 섞어 10번 반복
data = data.sample(frac=1).reset_index(drop=True)
print(find_B_pair(data))
알고리즘 개선
달리 토의할 만한 친구는 없어서 chatGPT에게 ‘생일 문제에 대해 코드를 썼는데, 이걸 개선할 방법이 있느냐’고 물어봤다.
답변 사항은 다음과 같다.
- 코드에 주석을 추가하면 다른 사람이 코드를 이해하는 데 도움이 된다.
* 주석을 한국어로 썼는데, 질문은 영어로 해서 지워뒀었다. 이후 한국어 주석이 그대로 있는 코드로 똑같은 질문을 다시 했으나 똑같은 지적이 돌아온 것으로 보아 GPT는 영어 주석을 요구한 것 같다. 아쉽게도 내가 아직 그 정도 수준은 못된다. - 보다 설명적인 변수 이름을 사용하라.
for루프에 사용된 변수k의 이름이 설명적이지 않다.
* 다음부터 적극 반영하겠음. 나도 웬만하면 이름은 알아보기 좋게 짓는데 오늘은k자리에 적당히 쓸 이름이 생각나지 않아서 대충 썼었다. if k['Birthday'] in table대신 try-except 블록을 사용하라. 사전에서 키가 존재하는지 확인하기 위해 if 문을 사용하는 대신 try-except 블록을 사용하여 보다 효율적으로 처리할 수 있다. 예를 들어 다음 코드를 사용할 수 있다:1 2 3 4
try: return (table[k['Birthday']], k['Number'], k['Birthday']) except KeyError: table[k['Birthday']] = k['Number']
* 좋은 참고가 되었다.
- 사전 대신 집합을 사용하라. 생일을 이미 본 적이 있는지 여부만 신경 쓰기 때문에 사전 대신 집합을 사용하여 생일을 저장할 수 있다. 집합은 상수 시간 조회가 가능하므로 이러한 용도로 사전보다 더 빠를 수 있다.
* 이건 GPT가 잘못 생각한 것 같다. 어차피 모든 쌍을 찾는 게 아니긴 했지만 결과를 반환할 때는 생일이 같은 두 사람의 정보도 함께 반환하기 때문에 집합을 이용해 생일만 따로 저장하면 안 된다. - 오류 처리를 추가하라. 코드에서는 데이터 집합에 생일이 같은 사람이 한 쌍 이상 있다고 가정한다. 이러한 쌍이 없는 경우를 처리하기 위해 오류 처리를 추가할 수 있다.
* 원래 코드에서는 생일 쌍이 없을 경우None을 반환하게 해 뒀지만, GPT가 지적한 문제는 쌍이 있는 경우에 반환하는 값의 자료형과 없을 경우에 반환하는 값의 자료형을 통일시키라는 의미인 것 같다. 내가 사용한 언어가 파이썬이 아니었다면 당연히 그렇게 해야 했겠지만 파이썬이라서 대충 쓴 건 맞다. 반성합시다.
* 나중에 GPT가 써준 개선 코드 예시를 봤는데, 결과를 출력하는 부분에서None이 반환되었을 경우일치하는 쌍이 없습니다같은 문구를 대신 출력하게 만들라는 뜻이었던 것 같다. 이 코드는 확인만 하면 되는 코드라 굳이 그렇게까지 쓰지는 않았었다. - 샘플링 코드를 함수 외부로 이동하라. 데이터를 샘플링하고 함수를 호출하는 코드를 함수 외부로 이동하여 함수의 모듈화 및 재사용성을 높일 수 있다.
* 이건 뭘 말하는 건지 모르겠다. 데이터를 섞기 위한 샘플링 코드를 말하는 거라면 이미 함수 밖에 있다.
* 개선 코드 예시를 봤는데if __name__ == '__main__':이 추가된 것 이외엔 별 다를 게 없었다. 정말로 어떻게 바꾸라는 건지 모르겠다.
GPT의 예시 코드는 생략하겠다. 그걸 그대로 가져다 쓸 마음은 없다. 바꿔도 내 맛대로 바꿔야 내 코드지.
수정한 알고리즘
chatGPT의 제안을 반영했다.
- 주석을 더 자세히 썼다.
- 대충 지은 변수명을 제대로 개명했다.
- 생일 쌍을 찾는 함수 내에서 테이블에 데이터가 존재하는지 확인하는 부분을
if-else에서try-except로 바꿨다. - 생일 쌍이 데이터에 존재하지 않았을 경우
None대신 “No pair”를 출력한다.
if __name__ == '__main__':은 필요성을 느끼지 못해 추가하지 않았다. 이 함수를 모듈로 쓸 생각이라면 추가하는 게 맞지만 현재로서는 이 함수를 모듈로 사용할 생각이 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
file_route = r'algorithm\homework\week01\Algorithms - Birthday Data edited.csv'
data = pd.read_csv(file_route, header=0, encoding='utf-8')
data.dropna(inplace=True) # 수강생 중 생일을 제공하지 않은 데이터는 제외
print(data.info())
def find_birthday_pair(_data): # 생일 쌍 찾기
table = {} # <class 'dict'>
for i in _data.index: # 데이터를 인덱스대로 순회
person = _data.iloc[i] # 데이터 하나씩 가져오기
try: # 테이블에 데이터가 존재한다면 다음 코드가 실행됨
return (table[person['Birthday']], person['Number'], person['Birthday']) # 생일 쌍 반환
except KeyError: # 테이블에 데이터가 존재하지 않았음
table[person['Birthday']] = person['Number'] # 테이블에 추가
return None # 반복을 다 해도 반환할 게 없었다면 None 반환
for _ in range(0, 10): # 데이터를 무작위로 섞어 10번 반복
data = data.sample(frac=1).reset_index(drop=True) # 데이터 섞기
result = find_B_pair(data)
print(f'{result if result is not None else "No pair"}') # 생일 쌍 찾기 결과 출력
진짜 이론대로 나오는지 실험하기
find_birthday_pair()함수는 위에서 정의한 것과 같다.- 1 ~ 365 중 하나를 뽑고 이를 월과 일로 환산하는 방식으로 랜덤한 생일을 생성한다. 굳이 환산하는 이유는 추가 궁금한 점 문단을 보면 알 수 있다.
n에 직접 숫자를 대입하여 사람 수를 정할 수 있다.total로 총 실행 횟수를 정할 수 있다.- 자세한 사항은 주석으로 써두었다.
n을 23으로 설정하고 코드를 실행하면 실제로 50% 이상의 확률이 나온다. 아래 코드를 응용해 실험한 결과는 다음 링크에서 확인할 수 있다.
https://www.kaggle.com/code/dapin1490/birthday-problem/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import pandas as pd
import random
def num_to_day(_num): # 1 ~ 365 사이의 수를 1년 중 날짜로 환산(윤년 제외)
md = [(1, 31), (2, 28), (3, 31), (4, 30), (5, 31), (6, 30), (7, 31), (8, 31), (9, 30), (10, 31), (11, 30), (12, 31)]
for n in md:
if _num <= n[1]:
return f'{n[0] :02}.{_num :02}'
_num -= n[1]
return None
def generate_days(_n): # 1 ~ 365 사이의 숫자를 랜덤하게 뽑고 날짜로 환산해 임의의 생일 데이터 생성
return {'Number': [i for i in range(1, _n+1)],
'Birthday': [num_to_day(random.randrange(1, 365+1)) for _ in range(0, _n)]}
cnt = 0 # 주어진 데이터에서 생일이 같은 사람의 쌍을 찾은 횟수
n = random.randrange(0, 100+1) # 사람 수
total = 500 # 총 실행 수
for i in range(0, total):
print(f'\niterate {i+1}')
random_data = pd.DataFrame(generate_days(n)) # 임의의 생일 데이터 생성
b_pair = find_birthday_pair(random_data) # 생일 쌍 찾기
if b_pair is not None: # 생일 쌍이 존재할 경우 카운트 증가
cnt += 1
print(b_pair) # 찾아낸 생일 쌍 출력(None이어도 출력)
print(f'n = {n}, rate = {cnt / total * 100}%') # 설정된 사람 수와 생일 쌍이 존재한 비율 출력
추가 궁금한 점
365일 중 하루를 뽑아서 어떤 날이 뽑힐 확률과, 12월 중 하나를 뽑고 그 달에 있는 28/30/31일 중 하루를 뽑아서 어떤 날이 뽑힐 확률이 같을까, 다를까?
확률과 통계는 많이 까먹었지만 내가 아는 선에서 생각해본다면 다를 것 같다. 365일 중 하루를 뽑는 건 모든 날짜가 동일하게 1/365의 확률을 갖지만, 달과 일을 따로 뽑으면 일자별로 뽑힐 확률이 다를 것 같다.
예를 들어 2월 28일이 뽑힐 확률이라고 치자. 365일 중 하루를 뽑는다면 1/365이다. 달과 일을 뽑는다면 1/12 * 1/28 = 1/336이다. 다른 거 맞네.
질문 하나만 더 해보자. 그렇다면 달과 일을 따로 뽑아도 모든 확률의 합은 1이 될까?
계산을 역순으로 생각해보자. 2월 28일이 뽑힐 확률은 1/12 * 1/28 = 1/336이었다. 이 확률은 2월 내의 모든 날짜가 동일하게 갖고, 그 합은 1/12이다. 그리고 1/12는 12월 중 2월이 뽑힐 확률과 같으며 이는 12개 월이 모두 동일하게 갖는다. 12개 월이 뽑힐 확률의 합은 1이다. 고로 달과 일을 따로 뽑으면 각 날짜가 뽑힐 확률은 동일하지 않지만 전체 확률의 합은 1이다.
참고 자료
- 생일 문제 - 위키백과, https://ko.wikipedia.org/wiki/생일_문제
- 파이썬의 딕셔너리는 어떻게 구현되어 있을까? -해시-, https://fierycoding.tistory.com/68
- Pandas에서 DataFrame 행을 무작위로 섞는 방법, https://www.delftstack.com/ko/howto/python-pandas/how-to-randomly-shuffle-dataframe-rows-in-pandas/
- 파이썬 난수(random) 생성, https://yeolco.tistory.com/95
- (Python) 숫자 포맷팅, https://jaeworld.github.io/python/python_number_format/
- [Pandas] 리스트, 딕셔너리 자료형을 데이터프레임, Series로 바꾸기, https://jimmy-ai.tistory.com/89
- chatGPT와 대화하기, https://chat.openai.com/chat