지능 퀴즈—고공에서 달걀 던지기

Source: Dev.to

출처

고성 인터뷰 질문

문제

100층 건물이 있고, 단단한 달걀 2개가 있다. 건물 위에서 달걀을 떨어뜨리면, 어느 층보다 높을 때부터 달걀이 깨지기 시작한다.
최악의 경우, 최소 몇 번을 던져야 반드시 이 임계 층을 찾을 수 있을까?

잘못된 생각

이분 탐색: 100 → 50 → 25 → 12 → 6 → 3 → 1
이 방법은 임계 층에 따라 던지는 횟수가 달라지며, 최악의 경우 최대 50번(실제로는 더 적게)까지 필요할 수 있다.

예를 들어, 임계 층이 49층이라면 첫 번째 달걀은 50층에서 깨지고, 이후 두 번째 달걀은 1층부터 차례대로 올라가며 49층까지 찾아야 한다.

올바른 생각

1. 문제 이해

• 임계 층이 어느 층이든 최악의 경우에 필요한 최대 투척 횟수를 최소화해야 한다.
• 두 개의 달걀 역할: 첫 번째 달걀은 구간을 나누는 데 사용하고, 두 번째 달걀은 그 구간 안을 한 층씩 탐색한다.

2. 핵심 아이디어

최악의 경우 첫 번째 달걀을 한 번 던질 때마다 남은 탐색 가능한 층 수 + 이미 던진 횟수가 일정하게 유지되도록 한다. 이렇게 하면 임계 층이 어디에 있든 전체 투척 횟수가 거의 동일하게 된다.

3. 구체적인 방법

1. 첫 번째 달걀을 14층에 던진다.
   • 깨지면 두 번째 달걀을 아래로 한 층씩 내려가며 탐색한다. 최악의 경우 14번이 필요하다.
   • 깨지지 않으면 두 번째 시도는 27층(14 + 13)에 던진다. 이때 남은 탐색 가능한 층 수는 13층으로 감소한다.
2. 이후 매번 감소시키는 층 수는 차례대로 12, 11, …, 1이 된다.
3. 이렇게 하면 임계 층이 어느 층에 있든 최악의 경우 전체 투척 횟수는 14번이 된다.

4. 첫 번째 층을 14로 정하는 이유

층 수 감소의 합이 100층을 커버해야 한다:

$$ 1 + 2 + 3 + \dots + n \ge 100 $$

이 부등식을 만족하는 가장 작은 정수 (n)은 (n = 14)이다.

---

따라서 위와 같은 감소 단계 전략을 사용하면 최악의 경우 14번만에 임계 층을 정확히 찾을 수 있다.