| [ QuizWit ] in KIDS 글 쓴 이(By): yhs (스프리웰) 날 짜 (Date): 2005년 9월 14일 수요일 오후 02시 58분 53초 제 목(Title): 술탄의 딸등 등... 어찌어찌하다가 예전의 술탄의 딸들 글타래를 다 읽어 보게 되었습니다. 원래 생각했던 문제가 있었는데, 술탄문제랑 비슷하다느 ㄴ느낌이 들어서 이 보드에 올릴려고 했었습니다. 제가 생각한 문제는 점심식사 식당고르기라는 문제인데, 한달동안 출장을 갔는데, 점심을 30번 먹어야 되고, 식당의 수는 충분히 많을때 몇번동안 새로운 곳을 시도하고, 그 뒤로 그중 가장 나은 곳을 계속 가야 하는가 하는 문제입니다. 질리는 건 논외로 하구요. 술탄문제와의 차이는 술탄문제는 맥시멈을 찾는 전략이고, 식당문제는 전체 지참금의 총합을 맥시마이즈 하는 문제라는 점이 있네요. 어쨌든 술탄의 딸들 글타래를 읽다 보니 환상님의 도발적인 오만함에 낚여 근무중에 몰래 제가 시뮬레이션을 해보고 말았습니다. 왜, 초기구간최대값을 택하고, 그 다음 만나는 더 큰값을 건너뛰고 그 다음 값을 택하는게 정보를 더 활용하는건지 알 수 없기도 하구요. 세가지 알고리듬을 다 돌려 봤습니다. 1번은 슬기님의 n 만큼의 구간최대값을 본후 그 보다 더 큰값이 나타나면 멈추는 방법. 2번은 전술한 환상님의 방법. 3번은 발켄님의 temp_max 방법입니다. 10년동안 컴퓨터가 많이 발달해서 결과가 금방금방 나오더군요. 일단 공주가 100 명일경우 10만번 정도 시도했습니다. 1번 방법은 예측된 대로 n=37 일때 37% 정도의 성공률을 나타내구요. 환상님의 방법은 n=12 에서 27% 정도의 성공률을 가집니다. 발켄님의 방법은 n=5 에서 36% 정도 입니다. 발켄님의 방법은 공주가 1000명, 10000명 일때 n=8,12 이고 36% 정도 되는 걸로 봐서 1번 방법과 같이 1/e 로 될것 같습니다. 참고로 제가 생각했던 식당문제의 경우 n 이 전체 시도횟수에 선형이 아니더군요. 대략 한달일경우 7번 시도, 100 이면 16번, 1000 이면 44 번 정도를 시도하는게 가장 좋더군요. |