이 글에서는 아래 문제에 대한 해결 방법을 단계별로 살펴보겠습니다.
문제 정의
40층 높이의 건물이 있다고 가정해 봅시다. 우리는 어떤 층에서 계란을 떨어뜨려도 깨지지 않는지(안전한 층), 그리고 어느 층부터 계란이 깨지기 시작하는지 확인하고 싶습니다. 이때 필요한 최소 시도 횟수(trials)를 구하는 것이 이 퍼즐의 목표입니다.
이 문제는 동적 프로그래밍(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 계란을 x번째 층에서 떨어뜨리면 두 가지 결과 중 하나가 발생합니다.
- 계란이 깨진 경우 → 남은 계란 (i-1)개로 아래층(x-1층) 범위를 확인해야 합니다.
- 계란이 깨지지 않은 경우 → 계란 i개로 위층(j-x층) 범위를 계속 확인해야 합니다.
- 두 경우 중 더 나쁜 상황(worst case)을 기준으로 삼되, 모든 층을 시도해 본 결과 중 최솟값을 선택하면 됩니다.
그럼 실제 구현된 코드를 통해 해결 과정을 살펴보겠습니다.
예제 코드
# 동적 프로그래밍
INT_MAX = 32767
# 최소 시도 횟수를 구하는 함수
def eggDrop(n, k):
# 테이블 초기화
eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
# 기저 사례(base case)
for i in range(1, n + 1):
eggFloor[i][1] = 1
eggFloor[i][0] = 0
# 계란이 1개뿐이라면 항상 j번의 시도가 필요함
for j in range(1, k + 1):
eggFloor[1][j] = j
# 나머지 테이블 채우기
for i in range(2, n + 1):
for j in range(2, k + 1):
eggFloor[i][j] = INT_MAX
for x in range(1, j + 1):
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
if res < eggFloor[i][j]:
eggFloor[i][j] = res
return eggFloor[n][k]
# 메인 실행부
n = 4
k = 40
print("Minimum number of trials in worst case scenario with " + str(n) + " eggs and "+ str(k) + " floors is " + str(eggDrop(n, k)))
실행 결과
Minimum number of trials in worst case scenario with 4 eggs and 40 floors is 6
실행 결과를 해석해 보면, 계란 4개와 40층 건물이 주어졌을 때 최악의 경우에도 6번의 시도만으로 안전한 층을 찾아낼 수 있다는 의미입니다.
코드의 모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 변수의 참조 관계는 위 그림에서 확인할 수 있습니다.
시간 복잡도
이 알고리즘은 세 겹의 반복문을 사용하므로 시간 복잡도는 O(n × k²)입니다. 여기서 n은 계란의 개수, k는 층의 개수를 의미합니다. 계란 수와 층수가 커질수록 연산량이 늘어나지만, 완전 탐색에 비해 훨씬 효율적인 접근 방식입니다.
결론
이 글에서는 동적 프로그래밍을 활용하여 계란 던지기 퍼즐을 파이썬으로 해결하는 방법을 알아보았습니다. 재귀적으로 문제를 작은 부분 문제로 나누고, 메모이제이션 테이블에 결과를 저장함으로써 최악의 경우에 필요한 최소 시도 횟수를 효율적으로 계산할 수 있었습니다.