| [ QuizWit ] in KIDS 글 쓴 이(By): ilusion (환상) 날 짜 (Date): 1997년06월19일(목) 18시59분40초 KDT 제 목(Title): MS마이크로 소프트 들어가는 방법 IV. 제 생각에는 게스트님이 제 의도를 파악못하신것같군요. :) 게스트님의 생각은 2^6, 2^7, 2^8 , 2^9 이런식으로 딱 떨어질경우에만 옳습니다. :) 문제는 n= 100 게라서 스티브가 아무리 악날하게 6번째까지 끌고갈려고해도 5번째만에 아니면 4번째만에 끝날수가 있지요. 1부터 100까지에서 첫번째 스티브에게 묻습니다. 50입니까? 그러면 위하고 아래하고 정확히 49개씩 나눠집니다. 그런데 바이나리 써치를 해나가다보면 위하고 아래하고 숫자갯수가 정확히 딱 같게 안떨어지죠. 직접 해보시면 알게되지만 binary search를 할때 worst case로 5번째 선택하는 시점에 worst case면 셈플이 3개가 남습니다. (* 밥먹으면서 쫌전에 해봤어요. 히히.. 이제부턴 제가 직접해보지않은 주장은 하지않겠습니다. * ) 그런데! 이제부터 저의 믿기지 않는 주장이 시작됩니다. 아마 biased binary search라는걸 아실껍니다. 0.5 0.5 의 확률로 양쪽으로 갈라지는게 아니라 0.47 0.53 의 확률로 양쪽으로 갈라지는 확률이 biased된경우입니다. 스티브가 악날하다고 가정할때 과연 스티브는 숫자를 어디다가 숨길까요? 0 이나 100 혹은 49나 51같이 binary search 를 하게될때 상대방이 상대방이 선택하게 되는 50 같은 숫자 바로 adjacent 한데다가 숨겨놓아야 합니다. 위에서 말했지만 4번만 선택하면 3개의 숫자뿐이 안남으니까 이게 바로 스티브의 전략입니다. biased binary search 를 전 다음과 같이 주장합니다. 50입니까? 하고 묻는게 아니라 "49입니까? " " 51 입니까?" 혹은 "48입니까? "52입니까?" 하고 묻는거지요. 계산이 좀 복잡해서 하지를 않았는데 biased 를 얼만큼 주어야 할지는 잘모르겠군요. 그러나 x, 1-x 의 확률로 나눠질때 x를 biase라고 정의를 한다면 x는 남아있는 숫자의 갯수의 함수입니다. x = x(n) 여기서 n = 1,2, search depth. 스티브가 악날하든 않하든 승산은 있습니다. 게스트님이 실수하신것은 binary서치가 완벽하게 이루어질수있는 log 2 로 딱나눠떨어질수있는 수하고 100이란 완벽하지 않은숫자하고의 차이점을 몰라서입니다. :) 반론이 기대되는군요. ---- Applied Math Mathematical Statistics Department of Math. Department of Math. and Stat. University of Toronto McGill University 정 무경 : chung@math.toronto.edu |