본문 바로가기
녹아웃 토너먼트 - 시합을 몇번이나 할까?

 

 

어제 포스팅을 하나 하고 나니, 이제 다시 블로그가 재미있어질려고 합니다. 라고 하니, 좀 아날로그적인 생각이려나. 벌써 블로그가 페이스북이니, 트위터에 비해서 아날로그적인가 라고 생각하니, 조금은 서글픕니다만. 블로그야 말로, 휘발성이 아니라, 완성도 있는 작품이라고 생각하는 건 좀 촌스러운 걸까요.

 

여튼, 다시 포스팅 부릉부릉을 하기 전에, 브레인을 부릉부릉 해야겠다는 생각입니다. 자, 문제!

 

매년 친절한 임베디드 시스템 개발자되기 강좌에서는 디버깅 대회를 엽니다. 이 대회는 단순하게 녹아웃 토너먼트 방식 (진 팀은 곧바로 탈락하고 이긴 팀끼리 또다시 경기를 벌이는 방법을 반복하여 최종 우승팀을 가리는 방식)으로 진행되는데, 워낙 출중한 임베디드 시스템 개발자들이 많아서 총 5127 팀이 경기에 참가했습니다.

 

자, 운영자인 저는 총 경기횟수를 빨리 알아야 하겠는데, 어떻게 하면 정말 근사하게 알아낼 수 있을까요?

 

- 이제부터 계속 몰랑몰랑 부릉 했으면 좋겠습니다.

 

 

 

정답을 말씀해주셔서 너무 제가 할말이 없습니다.
한 팀을 제외한 모든 팀이 져야 게임이 종료되므로,
한팀이 지는 게임은 1회 이므로, 
전체 팀 - 1 이 그 답입니다. 흠.

 

그러니, 5126 번 경기가 열리겠지요?

 

너무 스마트한 분들이라서, 제가 또 한번 할말을 잃었습니다.

 

Commented by 이런 at 2012/09/19 01:19
너무 간단하잖아요!

약 5000번 정도 되겠는걸요?
Commented by 히언 at 2012/09/19 17:18
과연 그럴까요?? 으하하
Commented at 2012/09/19 01:33
5126경기! 한 경기에 한 팀씩 탈락하는데 최종우승팀 나올려면 한 팀 빼고 나머지는 다 탈락해야하므로 전체 참가팀수 - 1 하면 총 경기수가 나오겠네요 ㅎㅎ
Commented by 히언 at 2012/09/19 11:36
오오!!! 그렇군요. 아름다운 방법으로 완벽한 논리이네요!!
Commented at 2012/09/19 13:25
5126번? 경기 수 = 팀 / 2 -> 몫을 계속 2로 나눠주면서 1이 나올때 까지의 몫을 모두 더한다. 홀수일 경우 다음 계산시에 +1 하여 계산 ex) 10개팀 = 10/2 (몫 : 5) 5 /2 (몫 : 2) 2 + 1 /2 (몫 : 1) 1 + 1 /2 (몫 = 1) 5 + 2 + 1 + 1 = 9 대충 규칙을 보니 팀 - 1하면 경기 수가 나오는거 같군요 완전히 증명하진 못했지만.. 대충 몇가지 경우 수를 해보니..
Commented by 히언 at 2012/09/19 13:39
오오오!
귀납적 접근법 완벽하시군요!!! 오오오.
※ 이 포스트는 더 이상 덧글을 남길 수 없습니다.
친절한 임베디드 시스템 개발자 되기 강좌 글 전체 리스트 (링크) -



댓글





친절한 임베디드 개발자 되기 강좌 글 전체 리스트 (링크) -