생일 문제 : 더 계산이 쉬운 방법을 찾기

생일 문제

방에 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(아무도 같은 생일을 공유하지 않음)

아무도 같은 생일을 공유하지 않을 확률 계산

그러면 아무도 같은 생일을 공유하지 않을 확률을 계산해 봅시다

1. 첫 번째 사람: 365일 중 아무 날이나 선택 가능 (365/365)
2. 두 번째 사람: 첫 번째 사람의 생일을 제외한 364일 중 선택 (364/365)
3. 세 번째 사람: 앞 두 사람의 생일을 제외한 363일 중 선택 (363/365)
4. ...
5. 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%를 넘습니다. 이는 확률 이론에서 우리의 직관이 얼마나 잘못될 수 있는지를 보여주는 좋은 예입니다.

또한 복잡한 확률 문제에서는 직접적인 계산보다 여집합을 이용한 접근이 훨씬 쉬울 수 있다는 중요한 교훈을 얻을 수 있습니다.

특히 "적어도 하나"와 같은 조건이 있는 문제에서 이 방법은 매우 유용합니다.