The Two Egg Problem

개요

 

코딩 인터뷰 문제라고 알려진 The Two Egg Problem 을 아래 두 링크를 따라가며 정리해본다.

공자는 생이지지(生而知之) 학이지지(學而知之) 곤이지지(困而知之)가 있다 하였다.

공자가 하고팠던 말은 결국은 세 부류가 모두 알게 된다는 것이고, 그 상황에서는 세 부류가 모두 같다는 것이다.

 

이런 문제에 힘이 들고, 공부할 필요성에 의문까지 들고는 했었는데

일단 곤이지지(困而知之)를 향해 달려본다.

 

링크: http://datagenetics.com/blog/july22012/index.html

유튜브 링크: https://youtu.be/3hcaVyX00_4

 

문제 정의

 

100 개의 층이 있는 건물에서 계란을 떨어뜨렸을 때에 깨지지 않는 가장 높은 층을 알아내보자.

계란이 안깨지면 층을 달리하며 계속 테스트 가능하며, 제공되는 계란은 2개이다.

가장 적은 회수로 알아내보자.

 

계란이 하나라면

 

대표적인 전략으로 divide and conquer 가 있듯이, 이런 문제에는 극단적인 상황을 가정해보면 도움이 된다.

문제에는 계란이 2개지만, 계란을 하나라 가정해보자. 이 경우에는 오직 하나의 방법밖에 없다.

1층부터 한 번씩 떨어뜨리며 올라가서, 깨지는 층 바로 아래층이 정답이 된다.

 

계란이 여러 개라면        

 

여러 개의 계란을 쓸 수 있다면 어떻게 될까?

이진탐색이 답이다. 이때의 횟수는 log2N 이 된다. 계산법은 링크 참고: https://jwoop.tistory.com/9

횟수는 log2(100) 이 된다.  LOG2(100) = 6.643856189774724 이니깐 7번이면 된다.

- log2(N) = 7 이라고 하면 N = 2^7 = 128 이 된다. 즉, 128층까지는 7번이면 해결된다.

 

 

계란은 2 개 입니다만

 

문제로 돌아가보자. 우리는 계란을 2개 가지고 있다.

 

방법1. 이진탐색을 쓴다면 최악의 경우 50번 떨어뜨려야 한다.

 

1) 정답이 49층인 경우: 처음에 50층에서 깨지고, 두 번째 계란으로 1층부터 테스트 한다면 50번 필요

2) 정답이 100 층인 경우: 처음에 50층에서 안 깨지고 두 번째 계란으로 52층 부터 테스트 한다면 50번 필요

 

방법2. 하나를 가지고 10층 단위로 올라가볼 수도 있다.   1) 10층, 20층, 30층, … 올라가다가 깨지면 2) 2 번째 계란으로 아래의 9층을 계산해보는 것이다.

구분 계란1 횟수 깨졌을때 계란2 최대 횟수 전체 10층 1 9 10 20층 2 9 11 30층 3 9 12 40, 50, 60, 70, 80, 90층 4, 5, 6, 7, 8, 9 9 13 to 18 100층 10 9 19   계란 1이 어디에서 깨지는 지에 따라 최대 시도 횟수가 12번에서 19번으로 변한다.

 

방법2 변형. 10층 이 아닌 12층으로 해보면 어떻게 될까?

 

구분	계란1 횟수	깨졌을때 계란2 최대 횟수	전체
12층	1	11	12
24층	2	11	13
36층	3	11	14
48, 60, 72, 84, 96층	4, 5, 6, 7, 8	11	15 to 19
100 층	9	2	11

 

계란 1이 어디에서 깨지는 지에 따라 최대 시도 횟수가 12번에서 최대 19번으로 똑같다.

 

 

Minimization of Maximum Regret

 

표현이 애매하여 원문 링크를 그대로 가져왔다. 위 방법 2는 첫번째 계란이 어디에서 깨어졌는지에 따라 최대 시도 횟수가 가변한다.

이걸 조금이나마 정규화 해보자. 계란 1이 어디에서 깨지건, 이후 계란 2로 시도해보는 횟수가 똑같게 만들어보는 것이다.

 

1-1) 계란 1이 첫번째 시도한 n 층에서 깨졌다면, 계란 2는 최대 n-1 번 떨어뜨려 봐야 한다. 1 + n - 1 = n

1-2) 계란 1이 첫번째 시도한 n 층에서 깨지지 않았다면, 다음에 계란 1은 n + n 층이 아닌 n + (n - 1) 층에서 던져야 한다.

- 그러면 만약 계란 1의 두 번째 시도에서 깨졌다면, 계란 2로 탐색할 층의 개수가 하나 줄어들기 때문이다.

2) 계란 1이 두번째 시도한 n + n - 1 층에서 깨졌다면, 계란 2는 최대 n - 2 번 떨어뜨려봐야 한다. 전체 시도는 2 + n - 2 = n

3) 즉, 첫번째 계란을 얼마만큼의 층 간격으로 떨어뜨리건 최대 시도 횟수는 동일해진다. Uniform

4) 그리고, 시도하는 층이 100 층을 넘지는 않을 것이다.

 

첫번째 시도 층	n
두번째 시도 층	n + (n - 1)
세번째 시도 층	n + (n - 1) + (n - 2)
...	...
마지막 시도 층	n + (n - 1) + (n - 2) + (n - 3) + (n - 4) + … + 1

 

5) 마지막 시도층은 100 층 이상이어야 한다.

n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100

따라서 1 + 2 + 3 + 4 + 5 + …  + n >= 100

위 둘을 더해주면 n(n+1) >= 200 이 되고, n(n+1)/2 >= 100 이 된다.

 

이차 방정식이므로 계산기를 돌리면 13.651 이 나온다. 정수로 하면 14층.

이로써 우리는 첫 번째 계란이 몇 번째 시도에 깨지든 상관없이 항상 동일한 최대 시도 횟수 14 를 얻게 되었다.

 

실제로  해보자

 

계란 1이 14층에서 깨지면	계란 2로 13번 더 시도	총 14번 시도
14 + 13층에서 깨지면	12번 더 시도	14
14 + 13 + 12 = 39	11	14
39 + 11 = 50	10	14
50 + 10 = 60	9	14
60 + 9 = 69	8	14
69 + 8 = 77	7	14
77 +  7 = 84	6	14
84 + 6 = 90	5	14
90 + 5 = 95	4	14
95 + 4 = 99	3	14
100	0	1번만 시도하면 되겠지?

 

소화 안되는 부분

 

정말 꼭 + 1 까지 계산하는게 최선인가 조금은 헷갈렸다.

그래서 1 을 x 로 바꿔서 수식을 짜보니 (n - x )(n + x + 1) / 2 >= 100 이 나왔다.

 

그래프 그려주는 사이트에서 그려보니 한눈에 이해됨

- 링크: https://www.desmos.com/calculator

 

 

 

 

계란이 세 개라면?

 

혹은 네 개, 다섯 개라면?

좀 더 생각을 늘여가보자.

 

전체 층 수를 k, 계란 수를 e, 계란을 떨어뜨린 층 수를 n 이라고 하자.

 

n 층에서 계란을 떨어뜨렸을때 1) 깨진다면, 체크해야 할 남은 층 수는 n-1 이 되고, 계란 개수는 e-1 개가 된다. 2) 안 깨진다면, 체크해야 할 남은 층 수는 k-n 이 되고, 계란 개수는 e 개가 된다.

 

우리는 두 경우중 최악의 시도 횟수를 골라야 함과 동시에, 가장 작은 시도 횟수를 보여주는 n 층을 찾아야 한다.

이것은 재귀적으로 구할 수 있으며, 처음에 소개한 유튜브 동영상이 이와 관련한 동영상이다.

 

유튜브 링크: https://youtu.be/3hcaVyX00_4

- 추후 유튜브 링크를 둘러볼 예정임

 

결과 그래프는 아래와 같다. (출처:  http://datagenetics.com/blog/july22012/index.html )

계란이 하나일 경우는 모든 층을 다 흝어야 하겠지만 (맨 왼쪽 그래프)

이후 개수가 늘어날 수록 최대 시도 횟수는 팍팍 줄어든다.