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