<p><br></p><p>지난번에 답만 달랑 적으니까 이해가 잘 안된다고 하신 분들이 계셔서 해설과 함께 정답을 올립니다.</p><p><br></p><p></p><p style="font-family: Verdana; font-size: 11.818181991577148px; line-height: 19.09090805053711px;">문제</p><p style="font-family: Verdana; font-size: 11.818181991577148px; line-height: 19.09090805053711px;">말 25 마리를 가지고있다.</p><p style="font-family: Verdana; font-size: 11.818181991577148px; line-height: 19.09090805053711px;"><br></p><p style="font-family: Verdana; font-size: 11.818181991577148px; line-height: 19.09090805053711px;">가장빠른 세마리를 찾아내기 위해서는 경주를 몇 번이나 시켜봐야되는가?</p><p style="font-family: Verdana; font-size: 11.818181991577148px; line-height: 19.09090805053711px;">- 타이머가 없어서 한경주에 다섯마리씩밖에 뛰게할수없다.</p><div><br></div><div>정답 및 해설</div><div><br></div><div>우선 타이머가 없다는 가정은 말을 경주시켜 시간으로 등수를 정하지 않고 뛰어서 누가 빠르냐로 결정하겠다는 뜻입니다.</div><div>만약 타이머가 있다면 트랙이 5개이면 5번만에 트랙이 25개면 1번에 결정되니까 문제가 너무 단순하지요.</div><div>우선 5개조로 나누어 5마리씩 뛰게하고 각조에 1등한 말끼리 뛰게하여 순서대로 ABCDE 조라고 이름을 붙이면 아래와 같이</div><div>됩니다. 즉 A조는 1등 중에서 또 1등한 말 A1과 처음에 A1와 같이 뛰었던 말이 속한 그룹을 말하는 것입니다. 나머지 조도 이렇게 나눕니다.</div><div>A   B   C   D   E</div><div>A1 B1  C1 D1 E1</div><div>A2 B2  C2 D2 E2</div><div>A3 B3  C3 D3 E3</div><div>A4 B4  C4 D4 E4</div><div>A5 B5  C5 D5 E5 </div><div><br></div><div>즉 A1 B1... E1 말이 각조에서 1등한 말이고 그 말들을 다시 경주시켜서 A1이 가장 빠른 말로 결정됩니다.</div><div>우린 쉽게 1등들끼리 시합한 결과가 A1 B1 C1 순이니까 1 2 3 등이 아니냐고 할 수 있겠지만 </div><div>문제는 A2가 B1 보다 빠를 수 있기 때문에 비교해 보지 않고는 알 수가 없습니다.</div><div>그래서 A2과 B1을 비교해서 A2가 빠르면 A2가 전체 2등이 됩니다. 왜냐하면 B1보다 빠른 말은 B C D E 그룹에서는 없기 때문입니다.</div><div>그러나 만약 B1이 빠르면 B1이 전체 2등이 됩니다.  그래서 2등까지 경주가 도합 7번이 됩니다.</div><div><br></div><div>이제 3등을 결정해야지요.</div><div>만약 2등이 A2 였다면 A3와 B1을 비교해야겠지요. 비교해서 빠른 말이 전체 3등이 됩니다.</div><div>그런데 2등 B1이였다면 남은 말 중에 가장 빠른 말은 같은조의 B2와 1등 그룹에 속했던 C1과 A그룹의 A2가 됩니다. 결정이 안된 말중에서 이 세말 보다 더 빠른 말은 존재하지 않고 이 세말은 비교해 보지 않아서 누가 빠른지 모르기 때문에 이 3말을 경주시켜서 1등한 말이</div><div>전체 3등이 됩니다.</div><div><br></div><div>이렇게 하면 어떤 경우던지 1번만 더 경주 시키면 되니까 2위까지 7번 3위까지는 8번의 경주로 1등 2등 3등이 결정됩니다.</div><div>더 빠른 방법은 A2 A3 B1 B2 C1 을 동시에 뛰게하면 7번으로 줄일 수 있지요</div><div> 1</div><div><br></div><div><br></div><div>이 문제의 핵심은 이미 뛴 말들의 순서가 정해져 있으면 그 중에서 가장 빠른 말만 찾아서 서로 경주시킨다는 원칙이 문제 풀이의 핵심입니다.</div><div>이런 문제는 전산학에서는 merge sort라는 방법으로 풀때 사용합니다. 구글이 아무래도 전산관련회사이니까 배운 기본개념을 실생활에 잘 적용하는 능력이 있는지를 테스트하는 것 같고 비 전공자가 이 문제를 접했을 때 얼마나 논리적으로 잘 생각하는가를 테스트하는 문제인 것 같습니다.</div><div><br></div><div>전산전공자들이 가장 들어가서 일하고 싶어하는 회사중에 하나가 구글입니다. 자유로운 분위기 꼭 회사가 학교같은 느낌을 주며 무한히 자신의 능력을 개발하고 싶어하는 곳이지요. 우리나라도 구글과 같은 벤쳐정신이 넘치는 회사가 많이 나왔으면 좋겠습니다. </div><p></p>