| [ QuizWit ] in KIDS 글 쓴 이(By): geust (W2lcome) 날 짜 (Date): 1997년06월19일(목) 17시53분08초 KDT 제 목(Title): Re: MS에 취직하는법 > >만약 바이너리 서치 트리의 터미날에 해당되는 수 중에서 하나를 >선택하면 어떻게 되나요? > 터미날에 해당하는 수... 즉 필요한 질문이 6개 내지는 7개가 필요한 숫자들을 와다다다 말하면 말이죠? 흠.. 일단 1번째, 2번째, ... , 5번째 까지의 모든 질문에 등장하는 숫자를 세어 볼까요. 1번째 질문은 50을, 내지는 51을 선택하겠죠. 1개 2번째 질문은 25, 75 를 (26, 76 등도 선택할 수 있겠지만 어쨋든) 선택할 수 있을꺼니까 2개. 3번째 질문은 4개, 4번째 질문은 2^3 = 8 5번째 질문은 2^4 = 16 다더하면... 31개네요. 아까 터미날에 해당하는 수가 그럼 69개가 되네요. log_2(69) = 6.10... 음. 그래도 최악의 경우 6번내지는 7번의 질문이 되겠네. 뭐, 이때는 그 최악의 경우가 될 숫자가 정해졌을 꺼니까 바로 그 숫자를 (worst of worst) 말하면 1번에 OK일까요.. 그런데 아까 Terminal Point(?)에 해당하는 숫자가 꼭 일정한것은 아니겠죠. 즉, 처음에 50을 선택할때와 51을 선택할때의 차이점에 의해서 결과가 달라질것이고,,, 흠... MS쪽에서도 "worst of worst"를 선택하는 전략을 어떻게 좀 다르게 했을 겁니다. 따라서 "원샷"에 그 숫자를 선택할 수 있을지는 의문이군요. 아, 실수군요. 위의 경우에도 5번의 질문에 31개의 숫자가 날라가기 때문에 남는 숫자는 38개... (Terminal of Terminal?) 이 남은 38개를 대상으로? 이제는 좀 승산이 있나.. 으윽, 그런데 그 38개가 정해진게 아니고, 그리고, 50을 선택하느냐, 51을 선택하느냐에 따라서 (처음에) 남을 숫자가 달라질꺼고, 과연 그렇게 2중으로 꼬아놓았을지도 의문이군요. 여기까지 생각하면 되겠죠? 더 생각을 해야 할까요. 원래 출제자의 의도를 벗어나고 있는것 같긴 한데. 어쨋든, 저는 "안한다"에 걸겠습니다. 그럼 이만. @아참, MS사에게 마음속으로 어떤 숫자를 생각하도록 하면 거의 100% 중간에 숫자를 바꿀꺼 같으니 처음에 생각한 숫자를 종이에 써서 손 못대도록 해야겠죠. 그 종이 지키는 경찰 부르고,...이거 난리가 아니네. MS 시로시로 |