장민석
가입: 2006년 9월 5일 올린 글: 165
|
올려짐: 2007년5월28일 17:29 주제: 오늘 수업 시간에 나온 퀴즈 |
|
|
문제: 상대가 1보다 큰 임의의 자연수를 생각했을 때 최소한의 예/아니오 질문만으로 그 수를 알아내는 방법을 고안하라.
오늘 수업시간에 여담으로 교수님께서 내신 퀴즈인데요.
제가 생각한 방법이 첫 번째 방법에 비해 퍼포먼스가 더 좋은 것을 증명할 수 있습니다. ^^;;
우선 첫 번째 방법은 다음과 같죠.
1) upper boundary를 찾습니다.
인용: | 2보다 큽니까?
4보다 큽니까?
8보다 큽니까?
.... |
이런 식이죠.
2) 만약 "아니오"라는 대답이 나오면 바이너리 서치로 답을 구할 수 있습니다.
필요한 질문 수 : 우선 상대가 생각한 수가 2^(n-1) 과 2^n 사이에 존재한다고 가정합니다. 그러면,
1)의 과정에서 n번의 질문이 필요하고
2)의 과정에서 n-1번의 질문이 필요하므로(바이너리 서치지만 이미 한번의 질문을 한 것과 마찬가지이므로)
언제나 2n-1 번의 질문이 필요하게 됩니다.
반면 제가 제시한 방법은 다음과 같습니다. 이진수 변환과정과 유사하죠.
1) 그 수는 2로 나누어집니까? 라고 물어보니다.
1-1) 만약 상대가 예라고 대답한다면: "그 수를 2로 나눈 수는 2로 나누어집니까?"
1-2)만약 상대가 아니오라고 한다면: "그 수에서 1을 뺀 수를 2로 나눈 수는 2로 나누어집니까?"
2) 그리고 1-2)의 경우에는 "그 수는 1입니까?"라는 질문을 앞서 한 번 더 해야 합니다. 아니면 1)의 과정이 언제 끝나는지 알 수 없기 때문이죠.
3) 2)에서 예라고 했다면, 이제 저는 그 수를 2진수로 변환한 수를 알고 있는 셈이므로 "그 수는 **입니까?"라는 한번의 질문만 더 던지면 됩니다.
필요한 질문 수: 역시 정답이 2^(n-1)과 2^n 사이에 존재한다고 가정합니다.
우선 기본적으로 이진수 변환을 위한 질문, 즉 ".....는 2로 나누어 떨어집니까?"를 위해 n번의 질문이 필요합니다.
또한 "1입니까?"라는 질문은 최선의 경우 1번, 최악의 경우 n번 필요합니다.
최선의 경우는 그 수가 2의 거듭제곱인 경우이고, 최악의 경우는 2의 거듭제곱-1인 경우입니다.
마지막으로 "그 수는 **입니까?"라는 1번의 질문이 더 필요합니다.
따라서 제 방법을 쓸 경우 n+2~2n+1 번의 질문이 필요합니다.
확률적 평균치는 (3/2)n + 3/2 번이 되겠지요.
따라서 n이 6이상인 경우 평균적으로 제 방법이 첫 번째 방법보다 적은 수의 질문만으로 문제를 해결할 수 있습니다. 최악의 경우라도 겨우 2번의 질문 차이가 날 뿐이지요. 그러므로 n이 크면 클수록 제 방법이 좀더 유리하게 됩니다.
다만 제 방법의 경우엔 질문의 길이가 너무 길어지게 되므로 현실적으로 수행시간은 오히려 증가할지도 모르겠네요. 하지만 실제로 우리는 "그 수를 2로 나눈 수를 2로 나눈...." 이런 식으로 얘기하지 않겠죠. 그저 "그 몫은 다시 2로 나누어지나요?"와 같이 이야기하겠지요. |
|