AncomWiki

말 25 마리 중 최속 3 선 찾기 문제 (구글 면접)

Properties1
description25 마리의 말 중 경주 (5 마리 동시) 를 통해 최속 3 위를 가려내는 최소 경기 횟수를 고민한 기록. 나이브한 방식 (6 회) 의 한계와 조별 예선 - 결선 방식 (7~8 회) 에 대한 추론 과정을 담고 있음.

38 min read

말 25 마리 중 최속 3 선 찾기 문제 (구글 면접)

Source

  • Basic Journals/Daily Journals/2023 계묘년/계묘년 32일, 2월 1일 수요일, 5주차.md

Summary

25 마리의 말 중 경주 (5 마리 동시) 를 통해 최속 3 위를 가려내는 최소 경기 횟수를 고민한 기록. 나이브한 방식 (6 회) 의 한계와 조별 예선 - 결선 방식 (7~8 회) 에 대한 추론 과정을 담고 있음.

Key Points

  • 문제: 말 25 마리, 트랙 5 개, 순위만 확인 가능할 때 최속 3 위 찾기 최소 경기 횟수
  • 나이브 접근: 5 개 조 예선 (5 회) + 1 위들 결승 (1 회) = 6 회. 단, 특정 조의 2~3 위가 전체 상위권일 수 있어 불완전
  • 대안 접근: 조별 구성을 겹치지 않게 하여 예선 - 결선 진행 시 7~8 회 소요 추정
  • 정답 여부 미확정: 저자가 7 회 또는 8 회로 추측 중이나 최종 검증은 안됨

그래프 뷰