계란 떨어뜨리기 문제

계란 떨어뜨리기 문제는 Google에서 유명해진 면접 질문이다. 문제의 전제는 간단하다. 특정 높이에서 물건을 떨어뜨려 깨짐 저항성을 평가하는 임무를 받는다. 간단하게, 여러 층으로 이루어진 건물 안에서 물건을 창문 밖으로 떨어뜨려 테스트한다:

목표는 물건이 깨지는 최소 높이를 찾는 것이다. 테스트할 물건이 1개만 주어진 단순한 경우를 생각해 보자. 테스트 샘플이 하나뿐이므로, 안전하게 1층부터 시작해 위층으로 올라가며 떨어뜨려야 한다:

물건이 매우 튼튼하다면, 세계에서 가장 높은 건물인 부르즈 할리파에서 테스트해야 할 수도 있다. 163층을 올라가야 하니 상당한 시간이 걸린다. 이 상황에서 불평을 하면, 고용주가 여러 샘플을 추가로 제공한다. 이 추가 샘플을 활용해 테스트 과정을 어떻게 빠르게 할 수 있을까? 이 상황에서의 문제가 바로 계란 떨어뜨리기 문제로 유명해졌다.

문제 설명

여러분은 m층 건물에 있고, n개의 달걀을 가지고 있다. 달걀이 깨지는 층을 찾기 위해 필요한 최소 시도 횟수는 몇 번일까?

문제를 이해하기 쉽게 몇 가지 규칙을 정리했다:

• 떨어뜨렸을 때 깨지지 않은 달걀은 다시 사용할 수 있다.
• 깨진 달걀은 버려야 한다.
• 모든 달걀은 떨어졌을 때 같은 영향을 받는다.
• 달걀이 깨지면, 더 높은 층에서 떨어뜨려도 깨진다.
• 달걀이 깨지지 않았다면, 더 낮은 층에서 떨어뜨려도 깨지지 않는다.

해결 방법

• eggNumber -> 현재 달걀의 개수
• floorNumber -> 현재 층 수
• visitingFloor -> 방문 중인 층
• attempts -> 달걀이 깨지는 층을 찾기 위해 필요한 최소 시도 횟수

모든 해결 방법을 2차원 배열에 저장한다. 행은 달걀의 개수를 나타내고, 열은 층 수를 나타낸다.

먼저 기본 케이스를 설정한다:

1. 달걀이 하나만 있다면, 층 수만큼 시도해야 한다.
2. 달걀이 두 개 있고 층이 하나라면, 한 번만 시도하면 된다.

for var floorNumber in (0..<(numberOfFloors+1)) {
    eggFloor[1][floorNumber] = floorNumber // 기본 케이스 1: 달걀이 하나라면 'numberOfFloors'만큼 시도해야 함
}

eggFloor[2][1] = 1 // 기본 케이스 2: 달걀이 두 개이고 층이 하나라면 한 번만 시도하면 됨

달걀을 'visitingFloor' 층에서 떨어뜨렸을 때 두 가지 경우가 발생할 수 있다:

1. 달걀이 깨지는 경우

2. 달걀이 깨지지 않는 경우

3. 달걀이 'visitingFloor' 층에서 떨어뜨린 후 깨진다면, 'visitingFloor'-1 층 이하를 남은 달걀로 확인해야 한다. 따라서 문제는 'visitingFloor'-1 층과 'eggNumber'-1 개의 달걀로 축소된다.

4. 달걀이 'visitingFloor' 층에서 떨어뜨린 후 깨지지 않는다면, 'visitingFloor' 층 이상을 확인해야 한다. 따라서 문제는 층 수-'visitingFloor'와 'eggNumber' 개의 달걀로 축소된다.

최악의 경우를 고려해 시도 횟수를 최소화해야 하므로, 두 경우 중 최댓값을 선택한다. 모든 층에 대해 위 두 경우의 최댓값을 계산하고, 그중 최소 시도 횟수를 선택한다.

기본 케이스와 이전에 찾은 답을 바탕으로 다음과 같이 답을 구한다.

attempts = 1 + max(eggFloor[eggNumber-1][floors-1], eggFloor[eggNumber][floorNumber-floors]) // 현재 시도를 고려해 1을 더함

if attempts < eggFloor[eggNumber][floorNumber] { // 최솟값 찾기
    eggFloor[eggNumber][floorNumber] = attempts
}

예제

2개의 계란과 2층짜리 건물이 있다고 가정해 보자.

1. 첫 번째 층에서 계란 하나를 떨어뜨린다. 만약 깨지면 답을 얻는다. 깨지지 않으면 2개의 계란과 1층이 남는다.
   시도 횟수 = 1 + 0(답을 얻은 경우)과 eggFloor[2][1] (기본 케이스 2로 1을 얻음) 중 최대값
   시도 횟수 = 1 + 1 = 2
2. 두 번째 층에서 계란 하나를 떨어뜨린다. 만약 깨지면 1개의 계란과 1층이 남는다. 깨지지 않으면 답을 얻는다.
   시도 횟수 = 1 + eggFloor[1][1](기본 케이스 1로 1을 얻음)과 0(답을 얻은 경우) 중 최대값
   시도 횟수 = 1 + 1 = 2
3. 2와 2 중 최소값은 2이므로, 답은 2이다.
   2는 계란이 깨지는 층을 찾기 위해 필요한 최소 시도 횟수이다.

Swift Algorithm Club의 Arkalyk Akash가 작성. Kelvin Lau가 수정 및 추가