게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

오늘 수업 시간에 나온 퀴즈

 
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.210 Principles of Programming (Spring 2007)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
장민석



가입: 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로 나누어지나요?"와 같이 이야기하겠지요.
위로
사용자 정보 보기 비밀 메시지 보내기
이광근



가입: 2005년 8월 29일
올린 글: 68

올리기올려짐: 2007년5월30일 12:05    주제: 인용과 함께 답변

좋은 생각.
그러나.
종이가 필요하지 않을까?

번시간을 메모리로쓰는.
좋은 예이구나.
위로
사용자 정보 보기 비밀 메시지 보내기 이메일 보내기 글 올린이의 웹사이트 방문
이전 글 표시:   
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.210 Principles of Programming (Spring 2007) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay