Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
계란 깨기(Egg Dropping) 문제는 주어진 E개의 계란과 F층짜리 건물에서 임계 층을 찾는 최소 낙하 횟수를 구하는 문제입니다. 이 문제의 핵심은 최악의 경우를 대비하여 계획해야 하며, 이는 재귀적으로 두 가지 하위 문제를 해결한 후 그 중 최대값을 취하는 방식으로 접근합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 Dev.to AI tag의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기Scrambled String은 서브스트링이 위치만으로는 확정되지 않고 길이도 필요했기 때문에 추가 차원이 필요했습니다. Egg Dropping은 또 다른 무언가를 필요로 합니다: 분할 지점 k는 이번에는 문자열 속의 장소가 아니라 건물의 실제 층수이며, 이 시리즈에서는 처음으로 결합 단계가 자신의 선택 결과를 확인하기 전에 전념해야 한다는 사실을 고려해야 합니다.
당신에게 E개의 계란과 F층짜리 건물이 있습니다. 여기에는 알려지지 않은 임계 층(threshold floor)이 존재합니다: 이 층이나 그 아래에서 떨어뜨린 계란은 살아남고, 이 층보다 위에서 떨어진 계란은 깨집니다. 당신은 가능한 한 적은 낙하로 이 임계점을 찾아내야 하지만, 미리 어떤 층에 임계점이 있는지 알 수 없기 때문에 최악의 경우를 대비하여 계획해야 합니다.
Floor: 1 2 3 4 5 6 7 8 9 10
ok ok ok ok ok break break break break break
여기서 임계점은 5층입니다. 그곳에서 떨어진 계란은 살아남고, 6층부터는 깨집니다. 만약 바닥부터 한 층씩 테스트한다면, 임계점이 시도하는 마지막 층일 수 있기 때문에 최악의 경우 F번까지 낙하가 필요할 수 있습니다. 목표는 가능한 가장 적은 최악의 경우 시도로 임계점을 찾는 전략입니다.
만약 당신이 k층에서 계란을 떨어뜨린다고 가정해 봅시다. 정확히 두 가지 결과가 있으며, 각각은 임계점이 어디에 있어야 하는지에 대해 다른 정보를 알려줍니다.
10
9
8
...
계란이 깨집니다 (The egg breaks). 임계점은 k층보다 아래여야 합니다. k층과 그 이상의 모든 층은 이제 깨진 것으로 알려졌으므로, 검색 공간은 1층부터 k-1층으로 줄어듭니다. 또한 계란 하나를 사용했기 때문에(방금 깨졌으므로), E-1개의 계란과 여전히 검색해야 할 k-1층이 남습니다.
subproblem: solve(E - 1, k - 1)
계란이 살아남는다. 임계점은 $k$ 이상이어야 한다. $k$보다 낮은 층들은 제외되고, 탐색 공간은 $k+1$부터 $F$까지가 되며, 이는 $F-k$개의 층을 의미한다. 계란이 살아남았으므로, 여전히 모든 $E$ 개의 계란을 가지고 있지만, 확인할 층의 수는 줄어들었다.
subproblem: solve(E, F - k)
k층에서 떨어뜨림
|
+----------+----------+
...
이 부분은 이 시리즈의 이전 모든 문제들과 비교했을 때 진정으로 새로운 부분이다. 당신은 이 두 가지 결과 중 어느 것이 발생할지 선택할 수 없다. 계란은 깨지거나, 아니면 깨지지 않으며, 당신은 그것에 아무런 통제도 할 수 없고, 미리 알 방법도 없다. 따라서 당신이 전념하는 어떤 전략이든 최상의 결과가 아니라, 최악의 가능한 결과로 평가되어야 한다. 이는 두 가지 분기가 이전 장에서 본 min이나 sum이 아니라 max로 결합됨을 의미한다:
1 + max(solve(E - 1, k - 1), solve(E, F - k))
여기서 +1은 방금 시도한 낙하를 계산하며, 이는 어떤 결과가 나오든 한 번의 시도로 간주된다.
핵심적인 움직임은 지금까지 이 시리즈의 모든 문제들과 동일하다: 가능한 모든 분할 지점을 시도하고, 두 개의 하위 문제를 해결한 다음, 그것들을 결합하는 것이다. 다른 점은 조합의 형태이다.
for k in range(1, F + 1):
이 계열의 이전 모든 문제는 $k$에 대한 min을 사용하여 최적의 분할 지점을 선택했다. 계란 깨기 문제도 그렇게 하지만, 한 가지 트위스트가 있다: 각 개별 $k$에서, 먼저 max를 사용하여 두 결과 중 더 나쁜 경우에 대비해야 하고, 그 후에야 다양한 값의 $k$에 대해 min을 사용하여 비교하며, 가장 작은 최악의 보장을 제공하는 층을 찾는다.
MIN (최적의 층 선택)
|
+------------+------------+
...```
이러한 최소 외부, 최대 내부 구조가 바로 이 문제의 실제 특징이며, 명시적으로 언급할 가치가 있습니다. 왜냐하면 이것이 진정으로 새로운 부분이기 때문입니다. 이 시리즈의 이전 모든 문제는 두 가지 중 하나만 필요했습니다: MCM(Matrix Chain Multiplication)은 `min`만 필요했고, 괄호 분할 (Palindrome Partitioning)은 `min`만 필요했으며, 불리언 괄호화 (Boolean Parenthesization)는 합계(sums)만 필요했고, Scrambled String은 부울 값인 `or`만 필요했습니다. 이 문제는 예측할 수 없는 적수에게 전략을 최적화하는 과정에서, 동시에 `min`과 `max` 둘 다를 중첩하여 필요로 하는 첫 번째 문제입니다.
dp(E, F) = min over 1 <= k <= F of { 1 + max(dp(E - 1, k - 1), dp(E, F - k)) }
## 기본 사례 (The Base Cases)
세 가지 조건에서 재귀가 종료됩니다.
**층이 남지 않은 경우 (`F == 0`):** 테스트할 것이 없으므로 시도 횟수는 0입니다.
**층이 하나 남은 경우 (`F == 1`):** 좁힐(narrow down) 것이 없으므로, 한 번 떨어뜨리는 것으로 결정됩니다. 따라서 어떤 경우든 시도는 1회입니다.
**계란이 하나 남은 경우 (`E == 1`):** 이것은 함께 고려할 가치가 있는 경우인데, 전체 분할 전략 자체가 더 이상 사용 불가능해지는 상황이기 때문입니다. 계란이 하나만 남아있으면, 높은 곳을 테스트하다가 깨질 위험을 감당할 수 없습니다. 왜냐하면 예비 계란 없이 한 번이라도 깨지면 더 이상 테스트를 계속할 수 없기 때문입니다. 남은 유일한 안전 전략은 가장 아래층부터 층별로 하나씩 테스트하는 것이며, 이는 최악의 경우 F번 시도가 필요하다는 것을 의미합니다. 즉, 깨지는 곳을 찾을 때까지 모든 층을 순차적으로 테스트해야 합니다.
if F == 0 or F == 1:
return F
...
[](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fng93fjuzds3fg9ko843d.png)
## 재귀적 해법 (The Recursive Solution)
class Solution:
def solve(self, E, F):
...
## 작은 예시: E = 2, F = 3
k = 2층에서 떨어뜨린다고 가정해 봅시다.
**만약 깨진다면:** 계란이 하나 남고, 아래로 확인할 층(1층)이 하나 있습니다. `solve(1, 1) = 1` 시도가 필요합니다.
**만약 살아남는다면:** 계란은 여전히 2개 남아 있고, 위에서 확인할 수 있는 층이 하나 더 있습니다 (3층). `solve(2, 1) = 1` 시도입니다.
시도 횟수 k = 2일 때 = 1 + max(1, 1) = 2
계란 2개와 층 3개를 가지고 첫 번째 낙하를 2층에서 하면, 첫 낙하가 어떤 결과로 나오든 관계없이 최대 2번의 시도 안에 임계점을 찾는 것이 보장됩니다.
## 동일한 상태를 표현하는 두 가지 방법
Scrambled String이 딕셔너리 버전과 인덱스 기반 버전을 통해 동일한 하위 문제를 설명했듯이, Egg Dropping 역시 층을 명시적인 범위 `(i, j)`로 모델링할지 아니면 단순한 개수 `F`로 모델링할지에 대한 동등한 선택지를 가집니다.
**명시적 구간:** 실제 층 경계를 추적하는 `solve(E, i, j)`. k에서 분할하면 깨지는 경우는 `i`부터 `k-1`까지가 되고, 살아남는 경우는 `k+1`부터 `j`까지가 됩니다.
min over i <= k <= j of { 1 + max(solve(E - 1, i, k - 1), solve(E, k + 1, j)) }
**상대적 범위:** 오직 테스트되지 않은 층의 개수만 추적하는 `solve(E, F)`. 절대적인 레이블은 추적하지 않습니다.
이 단순한 버전이 여기서 작동하는 이유, 그리고 이것을 알아차리는 것이 진정으로 유용한 점은 이 문제가 _어떤 특정 층_이 남아있는지에 관심이 없고 오직 _몇 개의 층_에만 관심이 있기 때문입니다. 전략의 관점에서 볼 때 4층부터 10층까지는 1층부터 7층까지와 동일하게 작동합니다. 왜냐하면 이 문제는 층의 절대 위치가 아니라 오직 검색해야 할 층의 개수만을 참조하기 때문입니다. 이것은 실제 문자가 각 위치에 중요했던 Palindrome Partitioning 같은 문제와 다릅니다. Egg Dropping의 하위 문제는 항상 개수에만 의존하므로, 2차원 상태 `(E, F)`는 이미 완전하며 Scrambled String의 `length` 차원이 요구했던 추가적인 인덱스 기록이 필요하지 않습니다.
## 메모이제이션: 2D 테이블
하위 문제 간에 변하는 것이 계란 개수와 남은 층 수, 단 두 가지뿐이기 때문에, `(E+1) x (F+1)` 크기의 테이블이 전체 상태 공간을 커버합니다.
F ->
E | 0 1 2 3 4 5 ...
---------------------
...
class Solution:
def solve(self, E, F, T):
...
이것은 이전 모든 챕터에서 봤던 동일한 메모이제이션 패턴입니다. 계산하기 전에 확인하고, 나중에 저장하는 방식이며, 키는 `(E, F)`를 사용합니다 (이전에는 `(i, j)`를 사용했었죠).
## 구간 DP 패밀리 비교
| | 분할점 | 하위 문제 | 조합 | 목표 | 상태 |
| --- | --- | --- | --- | --- | --- |
| MCM | 행렬 k 사이 | solve(i,k), solve(k+1,j) | left + right + 스칼라 비용 | min | 2D: T[i][j] |
| ... |
매 표의 모든 행은 동일한 골격, 즉 경계 조건, `k`에 대한 루프, 두 개의 하위 문제, 그리고 조합 규칙을 공유합니다. 실제로 챕터마다 바뀌는 것은 마지막 두세 개의 열에만 있습니다: 하위 문제가 무엇을 나타내는지, 어떻게 결합하는지, 그리고 상태가 몇 차원을 가져야 하는지입니다. 계란 깨기 문제는 이 표에서 새로운 종류의 분할점을 제시한 것이 아니라, 다른 모든 행이 이미 가지고 있던 `min` 아래에 `max`가 조합 단계 안에 처음으로 등장했다는 점이 진정한 기여입니다.
## 빠른 복습
Egg Dropping
|
층 k를 선택
...
'최소(min) 바깥, 최대(max) 안'은 이 문제의 특징이자, 단순히 비용을 최소화하는 것이 아니라 최악의 경우 보장(worst-case guarantee)을 최소화해야 하는 구간 DP 문제 전반에 걸쳐 나타나는 패턴입니다. `min`은 당신에게 주어진 가장 좋은 전략을 선택합니다. 반면, `max`는 일단 선택이 이루어진 후에는 그 결과가 당신의 통제 밖에 있다는 사실을 반영합니다.
## 이제 이해하게 된 것
계란 깨기 문제(Egg Dropping)는 이 시리즈 전체에서 구축해 온 정확한 분할 골격(partitioning skeleton)을 유지하지만, 양쪽의 두 하위 문제가 모두 당신이 통제하는 것이 아닌 첫 번째 문제입니다. 그중 하나는 당신에게 _발생하는_ 것입니다. 이것이 바로 `min` 안에 `max`가 처음으로 중첩되어 나타나는 이유입니다: 바깥쪽 `min`은 최고의 전략을 선택하는 당신이고, 안쪽 `max`는 어떤 결과가 더 나쁠지 대비하는 것이기 때문입니다. 왜냐하면 당신은 어떤 결과를 얻게 될지 결정할 수 없기 때문입니다.