| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2005년 1월 10일 월요일 오후 11시 57분 10초 제 목(Title): Re: [문제] 10연승? n연승자 만들기, greedy algorithm: 1. 2^n명이 참가할 수 있는 토너먼트 테이블을 만든다. 참가자 이름이 적힐 곳은 모두 공란이다. [ ] ... [ ] [ ... [ ] [ ] [ ] ... [1][2][3][4][5][6]...[2^n] 2. 대기자 리스트를 만든다. 초기에는 빈 리스트. 3. 대기자 리스트에 아무도 없다면 새 참가자를 불러서 대기자 리스트에 올린다. 4. 대기자 리스트에서 참가자를 하나 꺼낸다. 5. 참가자 이름을 적을 수 있는 곳 중 가능한 제일 왼쪽에 그 참가자를 적는다. 6. 시합이 열리는 것이 가능하다면 시합을 한다. 열 수 있는 시합이 없을때까지 반복. 우승자(n연승자)가 나오면 끝. 7. 지금까지 나왔던 모든 참가자들을 체크, 토너먼트의 현재 생존자와 시합한 적이 한번도 없다면 대기자 리스트로 보낸다. 8. 3으로 돌아간다. 예: 3연승자 만들기 . . . . . . . A . . . . . . . . . . A . . . A B . . . . . . . . . A . . . A B C . . . . . . A . A C . . A B C D . . . . . A . A C . . A B C D D . . . (중략) D A D A C D F A B C D D E F G 이방법으로 5연승과 6연승을 손으로 만들어봤는데 (각각 나름대로 가급적 난해한 방법으로) 5연승은 15~18명, 6연승은 28명이 나오더군요. n연승을 위해 필요한 최소 쪽수가 2^(n-1)보다 작을것 같기도 합니다. -- @< //) `//<_ 하얀까마귀 - http://outsider.egloos.com |