Drunk Passenger Problem 확률 문제 (cpp) ::

문제 : 100개의 좌석에 100명의 승객이 탑승 예정입니다. 하지만 1번 손님이 술에 취해 자기 좌석인 1번이 아닌 랜덤의 좌석에 앉아버렸습니다. 이후 다른 승객들은 자기 좌석에 누군가 앉아있다면 또 다른 랜덤한 좌석에 앉습니다. (없다면 자기좌석에 앉습니다.) 이때 100번 손님이 자기좌석인 100번에 앉을 확률이 얼마입니까?

cpp로 10000번 반복.

#include <iostream>
#include <vector>
#include <ctime>
/* 
Drunk Passanger Problem :: (100 Passengers)
Written By: bs-dev :: 2024-02-04
*/
using namespace std;
 
int main() {
    srand(static_cast<unsigned int>(time(nullptr))); 
 
    int simulations = 10000;
    int result = 0;
 
    for (int i = 0; i < simulations; i++) {
        vector<bool> seats(100, false); 
 
        seats[rand() % 100] = true;
 
        for (int i = 1; i < 99; i++) {
            if (!seats[i]) { 
                seats[i] = true;
            }
            else { 
                int freeSeat = rand() % 100;
                while (seats[freeSeat]) { 
                    freeSeat = rand() % 100;
                }
                seats[freeSeat] = true; 
            }
        }
        if (!seats[99]) result++;
    }
 
    double probability = static_cast<double>(result) / simulations;
    cout << "Result: " << probability << endl;
 
    return 0;
}

 

 

정답: 1/2 이다.

 

10000번 반복한 코드를 실행시켜보면 0.5가 나온다. 중요한건 구현이 아니었다. 

1번. 1/2은 확률적으로 생각하면 나올 수 있다. -> 컴퓨터한테 시키지 않아도 1/2 이 나온다.

2번. 재귀적으로 반복되는 구간이 있다. -> 코드로 더 간단히 구현 가능하다. 

3번. 100명이 아니라 1명부터 10명까지만 제한해서 예시를 보면 답은 다 1/2로 수렴한다.

 

완벽히 이해했다고 하기는 좀 그렇다. 세상에 똑똑한 사람은 많다.

1~3번 래퍼런스는 아래

 

1번 " 초봉 3억 외국 회사 면접 질문 " - YouTube

2번 술에 취한 승객 문제. 흥미롭고 어려워 보이지만... | by 리시 데이 차우두리(RishiDarkDevil) | 보통 (medium.com)

The Drunk Passenger Problem

3번  Quant Trader Interview Question | Probability (youtube.com)