생일 문제 : 더 계산이 쉬운 방법을 찾기
생일 문제
방에 n명의 사람이 있을 때, 적어도 두 사람(한 쌍)이 같은 생일을 가질 확률이 50% 이상이 되려면 n은 얼마나 커야 할까요?
많은 사람들이 직관적으로 "365의 절반인 약 182명 정도는 있어야하지 않을까 생각합니다." 그러나 실제 답은 이것보다 훨씬 작습니다. 왜 그럴까요?
우선 n명의 사람들 사이에 가능한 모든 비교 횟수를 계산해 봅시다. 각 사람이 다른 모든 사람과 생일을 비교한다면:
- 첫 번째 사람은 n-1명과 비교 ( 자신을 제외한 나머지 사람)
- 두 번째 사람은 n-2명과 비교 (첫 번째 사람과 자신을 제외한 나머지 사람)
- 세 번째 사람은 n-3명과 비교 (첫 번째, 두번째 사람과 자신을 제외한 나머지 사람)
- ...
이 합계는 가우스의 공식을 사용하면 n(n-1)/2가 됩니다. 예를 들어, n=20일 경우 비교 횟수는 190회입니다.
그런데 많은 사람들이 직관적으로 생각하는 "365일 중 절반 정도인 182.5명이 있어야 생일이 겹칠 확률이 50%가 될 것"이라는 생각과 비교하면, 20명만으로도 190번의 비교가 가능하고, 이는 이미 365/2 = 182.5보다 많은 비교 횟수입니다.
위와 같은 방법으로 구한 모든 쌍을 가지고 확률을 계산하기에는 너무 어렵습니다. 왜냐하면 세 명 이상이 같은 생일을 공유하는 경우 등 중복 계산의 문제가 있기 때문입니다.
여집합을 이용한 쉬운 접근법
이 문제를 해결하는 더 간단한 방법은 '여집합' 개념을 사용하는 것입니다:
적어도 두 명이 같은 생일을 공유할 확률 = 1 - 아무도 같은 생일을 공유하지 않을 확률
수식으로 표현하면: P(≥2명이 같은 생일) = 1 - P(아무도 같은 생일을 공유하지 않음)
아무도 같은 생일을 공유하지 않을 확률 계산
그러면 아무도 같은 생일을 공유하지 않을 확률을 계산해 봅시다
- 첫 번째 사람: 365일 중 아무 날이나 선택 가능 (365/365)
- 두 번째 사람: 첫 번째 사람의 생일을 제외한 364일 중 선택 (364/365)
- 세 번째 사람: 앞 두 사람의 생일을 제외한 363일 중 선택 (363/365)
- ...
- n번째 사람: (365-n+1)/365
이 확률들을 모두 곱하면 아무도 같은 생일을 공유하지 않을 확률이 됩니다.
P(아무도 같은 생일을 공유하지 않음) = 365/365 × 364/365 × 363/365 × ... × (365-n+1)/365
또는 P(아무도 같은 생일을 공유하지 않음) = (365! / (365-n)!) / 365ⁿ 로 표현할 수 있습니다.
실제 계산
이 공식을 계산해보면, n=23일 때 아무도 같은 생일을 공유하지 않을 확률이 약 0.493(50% 미만)이 됩니다. 따라서 적어도 두 명이 같은 생일을 공유할 확률은 약 0.507(50% 이상)입니다.
n=20일 경우, 계산하면 약 0.589의 확률로 아무도 같은 생일을 공유하지 않을 것이고, 따라서 약 0.411(41%)의 확률로 적어도 두 명이 같은 생일을 공유할 것입니다.
코드로 보기
- n명의 사람이 있을 때 적어도 두 명이 같은 생일을 가질 확률 계산 ( 여집합 활용)
func calculateBirthdayProbability(numberOfPeople: Int) -> Double {
// 아무도 같은 생일을 공유하지 않을 확률 계산
var probabilityOfNoDuplicates = 1.0
// 일반적인 해에는 365일이 있다고 가정
let daysInYear = 365
for i in 0..<numberOfPeople {
// i명의 사람이 모두 다른 생일을 가질 확률에 i+1번째 사람이 기존 생일과 겹치지 않을 확률을 곱함
probabilityOfNoDuplicates *= Double(daysInYear - i) / Double(daysInYear)
}
// 적어도 두 명이 같은 생일을 가질 확률 = 1 - 아무도 같은 생일을 공유하지 않을 확률
return 1.0 - probabilityOfNoDuplicates
}
- 전체 코드
struct BirthdayProbabilityPoint: Identifiable {
let numberOfPeople: Int
let probability: Double
var id: Int { numberOfPeople }
}
struct ContentView: View {
// 데이터를 저장할 배열
@State private var dataPoints: [BirthdayProbabilityPoint] = []
@State private var threshold: Int = 0
// 사용자 상호작용을 위한 변수
@State private var currentPeopleCount: Double = 1
@State private var currentProbability: Double = 0
var body: some View {
VStack(spacing: 20) {
VStack(spacing: 5){
Text("방에 n명의 사람이 있을 때")
Text("적어도 두 명이 같은 생일을 가질 확률")
}
.font(.title2)
.multilineTextAlignment(.center)
.padding(.horizontal)
.padding(.bottom)
if !dataPoints.isEmpty {
VStack(spacing: 15) {
HStack {
Text("사람 수: \(Int(currentPeopleCount))명")
.font(.title3)
.frame(width: 150, alignment: .leading)
Spacer()
Text("확률: \(String(format: "%.2f%%", currentProbability * 100))")
.font(.title3)
.fontWeight(.bold)
.foregroundColor(currentProbability >= 0.5 ? .red : .blue)
}
.padding(.horizontal)
// 슬라이더로 사람 수 조정
Slider(value: $currentPeopleCount, in: 1...100, step: 1)
.padding(.horizontal)
.onChange(of: currentPeopleCount) { newValue in
updateCurrentProbability()
}
}
birthdayProbabilityChart
.frame(height: 400)
.padding()
} else {
ProgressView("계산 중...")
.padding()
}
}
.onAppear {
calculateProbabilities()
}
}
// 생일 문제 차트
var birthdayProbabilityChart: some View {
Chart {
// 전체 데이터 포인트
ForEach(dataPoints) { point in
LineMark(
x: .value("사람 수", point.numberOfPeople),
y: .value("확률", point.probability)
)
.foregroundStyle(.blue.opacity(0.7))
.interpolationMethod(.catmullRom)
}
// 현재 선택된 사람 수에 해당하는 포인트 강조
if let currentPoint = dataPoints.first(where: { $0.numberOfPeople == Int(currentPeopleCount) }) {
PointMark(
x: .value("선택된 사람 수", currentPoint.numberOfPeople),
y: .value("선택된 확률", currentPoint.probability)
)
.foregroundStyle(.red)
.symbolSize(150)
}
// 50% 확률 지점 표시
if threshold > 0 {
RuleMark(
x: .value("50% 확률 지점", threshold)
)
.foregroundStyle(.red)
}
// 50% 확률 선 표시
RuleMark(
y: .value("50% 확률 선", 0.5)
)
.foregroundStyle(.red.opacity(0.5))
.lineStyle(StrokeStyle(lineWidth: 1, dash: [5, 5]))
// 현재 선택된 지점에 수직선 표시
RuleMark(
x: .value("현재 위치", Int(currentPeopleCount))
)
.foregroundStyle(.green.opacity(0.5))
}
.chartXAxis {
AxisMarks(position: .bottom, values: .automatic) {
AxisGridLine()
AxisValueLabel()
}
}
.chartYAxis {
AxisMarks(position: .leading, values: [0.0, 0.25, 0.5, 0.75, 1.0]) { value in
AxisGridLine()
let numValue = value.as(Double.self) ?? 0
AxisValueLabel("\(Int(numValue * 100))%")
}
}
.chartYScale(domain: 0...1)
}
// 생일 문제 확률 계산 함수
// 슬라이더 값에 따라 현재 확률 업데이트
func updateCurrentProbability() {
if let point = dataPoints.first(where: { $0.numberOfPeople == Int(currentPeopleCount) }) {
currentProbability = point.probability
}
}
func calculateProbabilities() {
// 백그라운드 스레드에서 계산 수행
DispatchQueue.global(qos: .userInitiated).async {
var newDataPoints: [BirthdayProbabilityPoint] = []
var foundThreshold = false
var thresholdValue = 0
// 1명부터 100명까지 계산
for n in 1...100 {
let probability = calculateBirthdayProbability(numberOfPeople: n)
newDataPoints.append(BirthdayProbabilityPoint(numberOfPeople: n, probability: probability))
// 50% 확률을 처음 넘는 지점 찾기
if probability >= 0.5 && !foundThreshold {
foundThreshold = true
thresholdValue = n
}
}
// UI 업데이트는 메인 스레드에서 수행
DispatchQueue.main.async {
dataPoints = newDataPoints
threshold = thresholdValue
// 현재 사람 수에 대한 확률 업데이트
updateCurrentProbability()
}
}
}
// n명의 사람이 있을 때 적어도 두 명이 같은 생일을 가질 확률 계산
func calculateBirthdayProbability(numberOfPeople: Int) -> Double {
// 아무도 같은 생일을 공유하지 않을 확률 계산
var probabilityOfNoDuplicates = 1.0
// 일반적인 해에는 365일이 있다고 가정
let daysInYear = 365
for i in 0..<numberOfPeople {
// i명의 사람이 모두 다른 생일을 가질 확률에 i+1번째 사람이 기존 생일과 겹치지 않을 확률을 곱함
probabilityOfNoDuplicates *= Double(daysInYear - i) / Double(daysInYear)
}
// 적어도 두 명이 같은 생일을 가질 확률 = 1 - 아무도 같은 생일을 공유하지 않을 확률
return 1.0 - probabilityOfNoDuplicates
}
}
#Preview {
ContentView()
}
정리
직관적으로는 방에 182명 정도가 있어야 생일이 겹칠 확률이 50%가 될 것 같지만, 실제로는 단 23명만 있어도 그 확률이 50%를 넘습니다. 이는 확률 이론에서 우리의 직관이 얼마나 잘못될 수 있는지를 보여주는 좋은 예입니다.
또한 복잡한 확률 문제에서는 직접적인 계산보다 여집합을 이용한 접근이 훨씬 쉬울 수 있다는 중요한 교훈을 얻을 수 있습니다.
특히 "적어도 하나"와 같은 조건이 있는 문제에서 이 방법은 매우 유용합니다.