바이트댄스 2차 면접 문제: 1000병의 술 중 하나에 독이 있다. 몇 마리의 쥐로 찾아낼 수 있을까?

AI 요약

1000병의 술 중 하나에 든 독을 찾기 위해 필요한 최소 쥐의 수는 10마리다. 각 쥐는 죽거나(1) 살거나(0) 두 가지 상태만 가지므로, 10마리로 2^10=1024가지 상태를 표현할 수 있어 1000병을 모두 커버 가능하다. 각 술병에 10비트 이진수 번호를 부여하고, 각 비트 위치에 해당하는 쥐에게 해당 비트가 1인 술의 샘플을 먹인 후, 죽은 쥐의 조합으로 독이 든 병을 특정한다.

핵심 포인트

• 10마리 쥐로 1024가지 상태 표현 가능 (2^10 = 1024 > 1000)
• 각 술병을 10비트 이진수로 변환 후, 비트가 1인 위치의 쥐에게 샘플 투여
• 죽은 쥐를 1, 산 쥐를 0으로 조합한 이진수를 십진수로 변환하면 독병 번호
• 이 문제는 비트맵(Bitmap)과 블룸 필터(Bloom Filter)의 원리를 테스트하는 고전적 면접 문제

향후 전망

• 대규모 데이터 처리에서 비트 연산과 상태 압축 기술의 중요성 지속 증가
• Redis 캐시 방어, 중복 제거 등 실제 시스템 설계에서 이진수 기반 최적화 패턴 활용 확대