General Egg Problem

개요

 

지난 번 계란 2개, 100층 건물이 주어졌을때의 The Two Egg Problem 을 풀어보았다.

- 링크: https://jusths.tistory.com/117

 

이번에는 임의의 계란 개수 e, 건물층수 k 일때의 해법을 찾아보자.

참고 링크: https://www.geeksforgeeks.org/egg-dropping-puzzle-dp-11/

 

문제

 

계란이 깨지지 않는 특정 층 수를 알아내는 최적의 투척 횟수를 찾아내는 것이다.

떨어뜨려도 깨지지 않으면, 다시 던질 수 있다.

계란, 건물은 상징적인 것이다. 물리적인 고려가 아닌 수학적인 관점에서 풀 것.

 

문제에 대한 접근

 

egg 개의 계란이 있는 상황에서 floor 층 건물의 n 층에서 계란을 던지면 1) 깨지거나 2) 안깨질거다.

1) 깨지면 egg-1 계란으로  cFloor-1 층 건물에 대한 문제로 줄어든다. (cFloor == current floor)

2) 안깨지면 egg 계란으로 floor-cFloor 층 건물에 대한 문제로 줄어든다.

 

이때 우리는 최악의 경우에, 최소의 계란 투척 회수를 찾아야 하므로

1) 2) 중에서 더 횟수가 많은 경우를 찾아야 한다.

 

여기까지의 내용을 Pseudo code 로 짜면 아래와 같다.

- 계란 개수 egg 개, 건물 층수 floor 층일때에, cFloor 층에서 계란을 던질때에 - 최소 계란 투적 횟수를 리턴해주는 함수를 eggDrop(egg, floor) 라고 하면, - eggDrop(e, k) 는 1) n 을 1 to k 층까지 모두 대입했을때에 2) 1 + min (max(eggDrop(egg-1, cFloor-1), eggDrop(egg, floor-cFloor))) 가 된다. → 즉, 가능한 모든 층수에서 던지는 각각의 경우의 최악의 투척횟수들 중에서, 가장 적은 값 + 1 인 것이다. → +1 은 방금 한 번 던진 것   예를 들어, 10층 건물이라면 1층에서 던진 경우부터 10층에서 던진 경우까지 각각 최악의 투척횟수를 구한 후 그 중에서 가장 적은 횟수를 리턴하는 것이다.

 

 

각각의 해결을 구현하여 깃헙에 올려본다. 자세한 설명은 GitHub 참고

GitHub: https://github.com/nicewook/egg_drop

* 최적의 층수까지 저장해두면 더욱 좋을 듯 하다.

 

재귀적 해결

 

1) 남은 층 수 (floor) 가 없다면 층 수 만큼 리턴하면 되고, 남은 계란 (egg) 가 하나 뿐이라면, 맨 아래부터 차근히 떨어뜨려야 한다.

2) 깨지는 경우 eggDrop(egg-1, cFloor-1) 을 계산하고, 깨지지 않은 경우 eggDrop(egg, floor-cFloor) 를 계산한다

3) Worst case 를 알아야 하므로 두 경우 중 Max 인 것이 결과이다.

4) 어디서 떨어뜨렸는가에 따라 결과가 달라지므로, 가장 결과값이 작은 경우를 리턴하면 된다.

 

 

Memoize 해결

 

재귀적 해결과 유사하지만

1) 맨 먼저, 이미 계산된 값이 있는지를 체크하여 있으면 리턴해준다. 없다면 아래로 진행

2) 남은 층 수 (floor) 가 없다면 층 수 만큼 리턴하면 되고, 남은 계란 (egg) 가 하나 뿐이라면, 맨 아래부터 차근히 떨어뜨려야 한다.

3) 그렇지 않다면, 재귀적으로 호출하여 값을 얻은 뒤 memo[egg][floor]에 기록해 둔 다음 리턴해준다.

 

 

 

BottomUp 해결

 

BottomUp 구현 참고링크: https://algorithms.tutorialhorizon.com/dynamic-programming-egg-dropping-problem/

 

맨 아래층부터 하나씩 계산하여 올라간다.

다만, 특정 계란 개수 e개, 특정 층수 cFloor 에서 최적의 투척횟수를 구할때는,

1 to cFloor 까지의 층수에서 던졌을때 각각의 worst case 중 가장 작은 값을 구한다는 것만 챙겨보자

 

 

Test 결과

 

Test 실행

go test -v -bench . --benchmem

 

아래는 테스트 결과이다.

재귀적 방법은 Test 기준이 다르니 무시해도 되고,

Memoize 가 BottomUp 보다 훨씬 빠른 것이 눈에 띈다. 솔직히 이유는 모르겠다…;;;