| [ QuizWit ] in KIDS 글 쓴 이(By): pinkrose (쭈쭈바) 날 짜 (Date): 1999년 6월 23일 수요일 오후 05시 19분 14초 제 목(Title): 마이크로소프트 -종대씨포스팅에 대한 설명 종대씨가 설명을 안하시길래 제가 종대씨포스팅에 대해서 똘을 굴려본결과 종대씨 포스팅을 이해하는 경지에 다다랐군요. ^^ 종대씨가 푸신문제는 n을 가장 크게 골라서 1부터 n까지 사이의 숫자가지고 바이나리써치를 할때 height of binary tree를 최대로 하는경우를 푼거쟌아요. 아마도 제 포스팅의 설명이 부족했던듯하군요. 빌게이트가 고르는건 1부터 100까지의 숫자중 하나인데 candidiate은 스무고개를 하거든요. candidate의 최고의 전략은 바이나리 써치라는건 의심의 여지가 없습니다. (지난번 토론의 기억으로는 끝에가서 binary search를 약간 modify했던걸로 기억합니다.) 빌게이트는 어떤숫자를 골라야하는데 이숫자를 고르면 candidiate이 바이나리 써치를 할경우 가장오래걸리게 만들어야 합니다. 예를들어보지요. 1,2,3,4,5,6이란숫자만 가지고 할때 분명 켄디데잇은 3이나 4를 고릅니다.( first guess) 만약 빌게이트가 1이란 숫자를 머리속에 생각하고있다고 합시다. 켄디데잇은 4를 찍었다고 생각해봐요. (첫번째 게스) 빌게이트는 4보다는 적다고 힌트를 줍니다. 그럼 당빠 1,2,3중하나니까 켄디데이트는 2를 찍습니다. (두번째게스 왜냐면 바이나리 써치니까 중간을 딱찍어야함) 그럼 이거보다 낮다고 빌게이트가 또힌트를 주고 고로 세번째가서야 간신히 맞추게됩니다. 즉 1부터 6번까지하게될경우 1이나 6을고를경우 가장 길게끕니다. 그런데 문제는 이렇게 가장 오래게스를 하게 만드는 어떠한 특정한 숫자를 찾는게 아니라 게스들의 평균치를 오래끌게만드는 그런숫자를 찾는겁니다. (문제의 정확한 스테이트먼트가 이래요. 그리고 이게 이문제에서의 how we defined optimality, so you have to solve the problem in this context and nothing else.) "인생은 예측불허. 그리하여 쭈쭈바의 의미를 찾는다" 쭈쭈바의 네딸들에서 "언제 오줌을 쌀건지는 예측불허. 그리하여 난 전봇대를 찾아헤멘다." 너의 쭈쭈바가 하늘을 날게하려면, 쭈쭈바에게 나는법을 가르쳐라. - McGill 수학과 1층 남자화장실에 쓰인 낙서. |