문제 : 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)
3번 Quant Trader Interview Question | Probability (youtube.com)
'Etc' 카테고리의 다른 글
ICT 공모전 후기 (5) | 2024.07.24 |
---|---|
Cpp map insert() & 범위 기반 반복문 (0) | 2024.03.14 |