| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2001년 11월 15일 목요일 오후 07시 18분 56초 제 목(Title): Re: 유명인 찾기 두 사람씩 짝을 짓는다. 사람의 수가 홀수일 경우 일단 한 명은 빼놓는다. 두 사람이 상대방을 아는지 확인한다. 두 사람 모두 상대방을 모르는 경우 둘 다 유명인이 아니다. 두 사람 모두 상대방을 알고 있는 경우 둘 다 유명인이 아니다. 두 사람 중 한사람만 상대방을 아는 경우 상대방을 모르는 사람들만 모은다. 위의 과정을 반복한다. 마지막에 남은 사람이 유명인이다. --- 마지막 남는 사람은 유명인이 될 수 있는 후보죠. 이 남은 사람이 유명인인지 확인하는 과정이 추가로 필요합니다. 필요한 질문 횟수는 6n번 가량... 좀 더 빠른 방법도 있습니다. 1. 임의의 두 사람 A와 B를 잡는다. 2. A에게 B를 아느냐고 묻는다. 3. A가 B를 알면 A를, A가 B를 모르면 B를 제거한다. (제거(?)된 인물은 유명인이 아니다.) 4. 위 과정을 한 명이 남을때까지 반복한다. (n-1번의 질문..) 5. 이제 남은 한 명에게 나머지 모든 사람을 아느냐고 묻는다. (안다면 유명인은 없다.) 6. 나머지 모든 사람에게 남은 한 명을 아느냐고 묻는다. (모른다면 유명인이 아니다.) 3n-3번. 더 정확히는 3n-4번에 가능. 더 적은 수로 되려나?? -- 박.. |