tvN '문제적남자'
세계 최고의 IT 기업 구글의 입사 시험은 단순히 지식을 묻는 것을 넘어, 극한의 상황에서 문제를 해결하는 논리적 사고력을 요구하는 것으로 정평이 나 있습니다. 최근 온라인 커뮤니티에서 다시금 회자되고 있는 '말 25마리 경주' 문제는 그 대표적인 사례로 꼽히며 수많은 이들의 두뇌를 자극하고 있습니다.
문제의 조건은 겉보기엔 단순하지만 생각보다 까다롭습니다. 총 25마리의 말 중에서 가장 빠른 상위 3마리를 찾아내는 것이 목적입니다. 하지만 한 번에 경주할 수 있는 말은 최대 5마리로 제한되어 있으며, 결정적으로 시간을 측정할 수 있는 타이머나 도구가 전혀 없습니다.
즉, 말들 사이의 상대적인 순위만 알 수 있을 뿐입니다. 각 말의 속도는 항상 일정하다는 가정하에, 가장 빠른 3마리를 확정하기 위해 필요한 최소 경주 횟수는 바로 7번입니다.
대다수의 지원자가 6번이라고 답하며 함정에 빠지곤 합니다. 우선 25마리를 5개 조로 나누어 각각 경주를 치러 각 조의 순위를 정합니다(5회). 이후 각 조의 1위들 5마리를 모아 한 번 더 경주를 하면 전체 1위는 확정할 수 있습니다(6회). 하지만 여기서 끝내면 2위와 3위는 알 수 없습니다.
예를 들어 전체 1위와 같은 조였던 2, 3위 말이 다른 조의 1위보다 빠를 가능성이 여전히 존재하기 때문입니다.
따라서 진정한 상위 3마리를 가려내기 위해서는 정교한 필터링을 거친 마지막 7번째 경주가 반드시 필요합니다. 6번째 경주에서 1위를 한 조의 2, 3위 말과, 2위를 기록한 조의 1, 2위 말, 그리고 3위를 기록한 조의 1위 말까지 총 5마리를 모아 최종 결승을 치러야 합니다.
이 문제는 과거 tvN '문제적 남자'에서도 다뤄지며 대중적인 관심을 끌었으며, 단순한 퀴즈를 넘어 데이터 정렬 알고리즘의 기초 원리를 담고 있어 전문가들 사이에서도 여전히 흥미로운 주제로 소비되고 있습니다.
