생일 역설이란?
생일 역설(Birthday Paradox)은 확률론 분야에서 가장 유명한 문제 중 하나입니다. 직관적으로는 같은 생일을 가진 사람이 등장하려면 많은 인원이 필요할 것 같지만, 실제로는 생각보다 훨씬 적은 인원만으로도 충분히 높은 확률이 나온다는 것이 이 문제의 흥미로운 점입니다.
문제의 정의는 다음과 같습니다.
생일 파티에 여러 명의 사람들이 모여 있고, 그중 일부는 같은 생일이 겹칩니다. 우리는 주어진 확률 조건을 만족하기 위해 필요한 대략적인 인원수를 구해야 합니다.
확률 개념 이해하기
확률의 기본 개념을 동전 던지기로 설명해 보겠습니다. 동전의 앞면이 나올 확률은 1/2이며, 10번 연속으로 앞면이 나올 확률은 약 1/1024, 즉 0.001에 불과합니다.
이제 생일 역설의 핵심 개념을 살펴보겠습니다.
윤년이 아닌 해(365일)를 기준으로, 두 사람의 생일이 서로 다를 확률은 다음과 같습니다.
364/365, 즉 1 − 1/365
첫 번째 사람은 어떤 생일이든 가질 수 있으므로 확률이 '1'이지만, 두 번째 사람부터는 생일이 겹치지 않을 확률이 점차 줄어듭니다.
P(다름) = 1 × (1 − 1/365) × (1 − 2/365) × (1 − 3/365) × (1 − 4/365) × ...
따라서 전체에서 '생일이 다를 확률'을 빼면 원하는 값을 얻을 수 있습니다.
P(같음) = 1 − P(다름)
예시 계산
같은 생일을 가진 사람이 존재할 확률이 0.70(70%)일 때 필요한 인원수를 구해 보겠습니다.
N = √(2 × 365 × ln(1/(1−p)))
N = √(2 × 365 × ln(1/(1−0.70))) ≈ 30
즉, 약 30명만 모여도 같은 생일을 가진 사람이 존재할 확률이 70%에 도달합니다. 이것이 바로 '역설'이라고 불리는 이유입니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
int findPeople(double p){
return ceil(sqrt(2*365*log(1/(1-p))));
}
int main(){
printf("%d",findPeople(0.70));
}
위 코드의 findPeople 함수는 목표 확률 p를 입력받아 필요한 최소 인원수를 계산합니다. C++의 log 함수는 자연로그(ln)를 사용하며, ceil 함수를 통해 결과값을 올림 처리하여 정수 형태의 인원수를 반환합니다.
실행 결과
30