우버와 에어비엔비가 영원히 변치 않을 것 같던 택시업과 호텔업을 새로 정의하고 있다. 컴퓨터 산업이 컴퓨터 안에서만 존재한다는 것은 옛날이야기가 되어버렸고, 이제는 영향을 받지 않는 업종을 찾기 힘들 지경이다. 그렇기에 많은 사람이 컴퓨터 교육에 관심을 두는 것은 당연한 절차 같다. 그래서 “Computer Science”에서 어떤 능력을 다루는지 단편적으로나마 적어보고자 한다. 유명한 Egg-Dropping Puzzle을 예로 들면서 이야기를 풀어보도록 하겠다.
문제 🔗
2개의 완전히 같은 달걀이 있다고 가정하자. 10층짜리 건물이 있을 때, 1 ~ N층에서 달걀을 떨어뜨리면 절대로 깨지지 않고, N + 1 ~ 10층에서 떨어뜨리면 반드시 깨진다. 깨지지 않은 달걀은 몇 번이고 재사용이 가능하며, 재사용을 해도 이 특성은 변하지 않는다. Egg-Dropping Puzzle은 이때, N을 최소 시도로 찾아내는 문제이다 (N은 0부터 10까지의 값 중 하나이다).
예를 들어, 달걀을 1층에서부터 차례로 떨어뜨리는 전략을 사용한다고 해보자. 이를 “전략 A”라고 부르자. N = 0이라면 단 한 번의 시도를 통해 N값을 알 수 있다. 1층에서 바로 깨졌기 때문이다. 하지만 N = 5일 때는 6번의 시도를 해봐야 한다. 5층에서 떨어뜨렸을 때 깨지지 않던 달걀이 6층에서는 깨질 것이기 때문이다. 이 전략은 N = 10일 때는 10번의 시도를 해보아야 한다. 즉, 전략 A는 최악의 경우 시도횟수가 10이다. Egg-Dropping Puzzle은 이 최악의 경우 시도 횟수를 최소화하는 것이 목적이다. (이런 문제에 익숙지 않다면 굉장히 헷갈릴 수 있으니 주의를 기울이기 바란다.)
풀이 🔗
위에서부터 차례로 떨어뜨리는 전략을 사용한다고 해보자. 이를 “전략 B”라고 부르자. N = 10이라면 단 한 번의 시도를 통해 N값을 알 수 있다. 10층에서도 깨지지 않기 때문이다. 하지만 N이 10보다 작으면 첫 시도 만에 달걀이 하나 깨져버린다. N이 9보다도 작으면 두 번째 시도에서 두 번째 달걀이 깨지고, 우리는 더 시도를 할 수 없다. 즉, N의 정확한 값을 알아내지 못하는 것이다. 여기서 우리는 달걀이 한 개 남았을 경우, 무조건 전략 A를 써야 함을 알 수 있다. 그럼 전략 B를 약간 수정해서 위에서부터 차례로 떨어뜨리되 달걀이 하나만 남으면 1층에서부터 떨어뜨린다고 하자. 이 경우 N = 5이면 7번의 시도를 해봐야 한다. 10층에서 떨어뜨려서 달걀이 하나 깨지고, 1층부터 5층까지는 달걀이 깨지지 않다가 6층에서 두번째 달걀이 깨지기 때문이다. 전략 B는 N = 9일 때, 10번의 시도를 해보아야 한다. 즉, 전략 B의 최악의 시도 횟수도 10으로 전략 A와 같아진다. 그럼 최악의 시도 횟수는 10일 수밖에 없을까?
다행히 그렇지는 않다. 첫 번째 시도에서 달걀을 5층에서 떨어뜨린다고 해보자. 이 경우 N이 5보다 작으면 달걀은 깨질 것이고, N이 5 이상이면 깨지지 않을 것이다. N이 5보다 작으면 달걀이 하나만 남으므로 전략 A를 써야 하고, 이 경우 최악의 시도 횟수는 N = 4일 때의 5회이다. N이 5 이상이면 달걀이 두 개 남으므로 8층에서 떨어뜨림으로써 최악의 시도 횟수를 5회보다 줄일 수 있다. 이 전략이 앞의 두 전략보다 획기적으로 나아졌음을 확인할 수 있다!
그렇다면 최고의 전략은 무엇일까? 이 문제를 짧게 정의하자면 10층짜리 건물에서 두 개의 달걀로 N값을 찾아내는 문제이다. 이를 x층짜리 건물에서 y개의 달걀로 N값을 찾아내는 문제로 바꿔서 생각을 해보자. 그리고 그 시도 횟수를 D(x, y)라고 정의하자. 그러면 우리가 원하는 값은 D(10, 2)가 된다. 우리는 첫 번째 달걀을 1층에서 떨어뜨릴 수도 있고, 2층에서 떨어뜨릴 수도 있고, 10층에서 떨어뜨려 볼 수도 있다. 이를 i 층에서 떨어뜨렸다고 하자. 만약 N < i라면 달걀은 깨질 것이고, 한 개의 달걀을 가지고 1 ~ i-1 층을 확인해봐야 한다. 이는 D(i-1, 1)와 같다. 만약 N >= i라면 달걀은 깨지지 않을 것이고, 두 개의 달걀을 가지고 i + 1층 ~ 10 층을 확인해봐야 한다. 그런데 i + 1층 ~ 10층을 확인해보는 것은 1층 ~ 10 – i층을 확인하는 것과 같으며, 이는 D(10-i, 2)와 같다. 즉, 첫 시도로 i층에서 떨어뜨리는 전략을 사용하면 최악의 시도 횟수는 D(i-1, 1)와 D(10-i, 2) 중 큰 값 + 1이 된다. +1은 이미 시도를 1회 했기 때문에 고려되었다 (둘 중 큰 값임에 주의하자. 우리가 구하는 값은 최악에 대한 값이기 때문이다). 최고의 전략을 찾기 위해 우리는 i를 1 ~ 10까지 변경해보면서 최소값이 되는 경우를 찾기만 하면 된다!
그런데 위에서 확인했듯이 달걀이 하나만 남은 경우 우리는 전략 A를 써야 함을 알고 있다. 즉, D(i, 1) = i이다. 남은 것은 달걀이 깨지지 않은 상태에서 D(10-i, 2)에 대한 확인이다. i=10일 때 달걀이 안 깨졌다는 것은 N=10이라는 의미이므로 더 고려할 필요가 없다. 남은 것은 i = 1~9일 때, D(1, 2), D(2, 2), …, D(9, 2) 값의 확인이다. 문제가 더 복잡해진 것처럼 보일 수 있는데, 조금만 더 인내심을 갖고 차근차근 확인해보자. 아래와 같이 표를 이용하면 무엇을 계산하는지 조금 더 명확해진다.
| 1층 | 2층 | 3층 | … | 10층 | |
|---|---|---|---|---|---|
| (달걀) 1개 | D(1, 1) | D(2, 1) | D(3, 1) | … | D(10, 1) |
| 2개 | D(1, 2) | D(2, 2) | D(3, 2) | … | D(10, 2) |
[1] D(1, 2)
D(1, 2)=1이다. 택할 수 있는 행동은 1층에서 달걀을 떨어뜨려 보는 것 하나이며, 그 결과에 따라 N이 0인지 1인지 판명이 된다.
| 1층 | 2층 | 3층 | … | 10층 | |
|---|---|---|---|---|---|
| (달걀) 1개 | 1 | 2 | 3 | … | 10 |
| 2개 | 1 | ? | ? | … | ? |
[2] D(2, 2)
D(2, 2)를 계산하기 위해서는 1층에서 떨어뜨려 보는 것과 2층에서 떨어뜨려 보는 두
행동을 비교하여 더 작은 값을 취하면 된다. 1층에서 떨어뜨린 경우, 달걀이 깨지면 N
= 0인 것을 알 수 있다. 달걀이 깨지지 않으면 위와 같은 논리로 D(1, 2) 값을 알아야
한다. 우리는 이미 D(1, 2)=1인 것을 알기 때문에 1층에서 떨어뜨린 것이 최적이라면
D(2, 2)=2가 된다. 2층에서 떨어뜨린 경우, 달걀이 깨지면 D(1, 1)를 알아야 하는데,
이미 D(1, 1)=1인 것을 알고 있다. 달걀이 깨지지 않으면 N=2인 것을 바로 알 수
있다. 즉, D(2, 2)=2가 된다.
| 1층 | 2층 | 3층 | … | 10층 | |
|---|---|---|---|---|---|
| (달걀) 1개 | 1 | 2 | 3 | … | 10 |
| 2개 | 1 | 2 | ? | … | ? |
[3] D(3, 2)
이런 식으로 D(3, 2)를 구하기 위해서는 D(1, 1), D(2, 1), D(1, 2), D(2, 2)를
알아야 한다. 표에서는 모두 좌측에 있는 셀들이다. 우리는 모두 알고 있으므로
차근차근 계산해보면 2층에서 떨어뜨리는 것이 최선이며, D(3, 2)=2라는 것을 알 수
있다. 이런 식으로 단순 계산을 반복하면 D(10, 2)도 구할 수 있게 된다.
코딩 🔗
위에서 우리는 답을 구하는 방법을 찾았다. 이를 전산과에서는 Algorithm이라고 한다. 무한한 인내력을 갖고 D(10, 2)를 구할 수도 있겠지만 그런 방법에는 한계가 있다. 예를 들어, D(1000, 20) 과 같은 값을 구하기 위해서는 아마 몇 시간의 노동이 들어갈 것이다. 게다가 중간에 계산 실수가 나올 확률도 높다. 여기서 단순 노동에 강한 컴퓨터의 힘이 나온다. 코드 몇 줄이면 임의의 층수와 달걀 수에 대해 답을 계산해주는 프로그램을 만들 수 있다. (글 하단에 첨부되어 있다.)
결론 🔗
이 문제를 푸는 데 있어서 다음의 과정을 거쳤다.
- 현실의 문제를 수학적 문제로 추상화: 달걀과 건물이 수식으로 표현됨.
- 추상화된 문제를 논리적으로 풀이:
D(10, 2)를 구하기 위해 어떤 값을 계산해야 하는지 정리됨. - 논리적 풀이를 코드로 구현: 논리대로 작동하는 프로그램이 완성됨.
Computer Science란 현실의 문제를 논리적 사고와 계산력을 잘 결합하여 풀어내는 학문인 것 같다. 그리고 이 계산력이 강력해지면서 기존에는 풀리지 않던 문제들이 풀리고, 새로운 기회들이 생겨난다. 위에서 강조하고 싶은 부분은 코딩이 Computer Science의 전부가 아니라는 것이다. 위 문제에서는 3번 단계에 도달하기까지 컴퓨터는 언급도 되지 않았다. 오히려 “문제 이해 능력”, “추상화 능력”, “논리력” 등이 더 주요했다.
물론 위 문제는 단순한 형태의 문제를 다루는지라 Computer Science에서 어떠한 것들을 다룬다고 얘기하는 데는 명확한 한계가 있다. 그저 하나의 문제를 해결하는 데 있어서 코딩 능력뿐 아니라 다양한 능력이 필요하다는 점을 적어두고 싶었다. 또한, 어떻게 컴퓨터의 힘이 사람이 해결할 수 있는 문제의 범위를 확장해주는지도 보여주는 흥미로운 예라고 생각한다.
첨부 코드 🔗
아래 코드는 실제로 작동하는 코드이다. http://www.tutorialspoint.com/compile_cpp11_online.php 페이지에 같은 코드를 넣고 compile 버튼을 누른 뒤, execute 버튼을 누르면 맨 아래의 화면에서 확인해볼 수 있다. (execute를 누른 뒤 천천히 타자를 쳐야 작동하는 것 같다) 1,000층짜리 건물에서 달걀이 100개가 있는 경우에 대해서도 바로 답을 구하는 것을 볼 수 있다. 방법을 조금 개선하면 100,000층짜리 건물에서 달걀이 100개 있을 경우의 해답도 1초면 구할 수 있을 것이다. ∎
#include <iostream>
#include <cstring>
#define MAX_FLOOR 1000
#define MAX_EGG 100
using namespace std;
int _D[MAX_FLOOR + 1][MAX_EGG + 1];
int D(int N, int eggs)
{
if (eggs <= 0) return -1;
if (N <= 0) return 0;
if (eggs == 1) return N;
if (_D[N][eggs] == -1) {
_D[N][eggs] = N + 1;
for (int i = 1; i <= N; ++i) {
int fail_val = D(i - 1, eggs - 1);
int succ_val = D(N - i, eggs);
int val = max(fail_val, succ_val) + 1;
if (_D[N][eggs] > val) {
_D[N][eggs] = val;
}
}
}
return _D[N][eggs];
}
int main()
{
memset(_D, 0xff, sizeof(_D));
int N, eggs;
cout << "몇 층짜리 건물인가요? (최대 " << MAX_FLOOR << ")";
cin >> N;
cout << "몇 개의 달걀이 있나요? (최대 " << MAX_EGG << ")";
cin >> eggs;
if (N <= 0 || N > MAX_FLOOR || eggs <= 0 || eggs > MAX_EGG) {
cout << "잘못 입력하였습니다." << endl;
return 0;
}
cout << D(N, eggs) << "번의 시도가 최적입니다." << endl;
return 0;
}