d라이브러리

어려운 개념을 익히느라 수고하셨으니 이번엔 재미있는 퀴즈 시간을 즐겨 봅시다. 이 문제를 풀어낸 사람은 제 후계자가 될… 앗, 아니아니 퀴즈를 맞혔다는 보람을 얻을 수 있습니다. 문제를 듣고 정답이 떠오른 사람은 머리 위에 개구리 초콜릿을 얹어주세요. 제가 살짝 가서 귓속말로 답을 듣겠습니다. 

퀴즈 설사약이 든 초코케이크를 판별하는 최적의 방법은?

“이런, 문제가 생겼습니다. 3번 제조실에서 초코케이크 재료에 설사약이 섞였다고 하네요. 어느 초코케이크에 설사약이 들어갔는지 확인을 해야 하는데, 겉보기엔 아무 차이가 없고 특별한 냄새도 나지 않아서 먹어서 확인해볼 수밖에 없습니다. 이 설사약은 아무리 조금 먹어도 딱 세 시간 뒤면 반응이 오고 일주일간은 화장실에 갇혀있다시피 해야 합니다. 그런데 3번 제조실에서 오늘 만든 초코케이크는 무려 8192개나 됩니다. 움파룸파 한 명 당 케이크 하나씩 먹어보게 하고 3시간을 기다리면 가장 확실하겠지만, 8192명이나 시식에 불러왔다가는 공장이 제대로 돌아갈 수 없어요! 3시간 안에 반드시 설사약이 든 초코케이크를 찾아내면서 시식할 움파룸파 수는 최소한으로 줄일 방법을 찾아 주세요.”

어떻게 하면 최적의 방법으로 설사약이 든 초코케이크를 찾아낼 수 있을까요? 한 케이크 당 한 명씩 움파룸파를 배치하는 건 확실하지만 효율이 아주 낮은 방법입니다. 어떤 아이디어가 효율을 높이면서 설사병에 걸릴 움파룸파의 수는 최소로 할 수 있을까요.

먼저 케이크가 2개인 상황으로 생각해보겠습니다. 케이크가 2개라면 필요한 최소한의 움파룸파는 1명입니다. 1개만 먹어보고 3시간 뒤 움파룸파가 설사병에 걸리지 않으면 나머지 한쪽에 약이 들어있을 거고, 설사병에 걸리면 먹은 쪽에 약이 들어있다는 뜻이니까요. 

그럼 케이크가 4개일 땐 어떨까요? 

이제 움파룸파 1명으로는 약이 든 케이크를 찾기 어렵습니다. 1명만 더 데려와서 2명으로 찾을 방법을 생각해보겠습니다. 움파룸파 2명을 각각 A, B라고 할 때 첫 번째 케이크는 아무도 먹지 않게 하고, 두 번째 케이크는 A만 먹고, 세 번째 케이크는 B만 먹고, 네 번째 케이크는 둘 다 먹게 합니다. A만 배탈이 나면 2번 케이크에 약이 들었을 것이고 B만 배탈이 나면 세 번째 케이크에, 둘 다 배탈이 나면 네 번째 케이크, 둘 다 멀쩡하면 첫 번째 케이크에 약이 들었다는 걸 알 수 있습니다. 어떤 원리인지 감이 오나요? 

비법은 바로 2진수를 활용하는 것입니다. 케이크 4개를 시식할 때는 각 케이크에 00, 01, 10, 11의 2진수를 부여하고 첫 번째 자릿수에 1이 있을 땐 A가 먹고 두 번째 자릿수에 1이 있을 땐 B가 먹는 방법으로 규칙을 정하는 겁니다. 이 규칙을 보기 쉽게 나타내면 다음과 같습니다.

이렇게 나타내면 어떤 조합으로 케이크를 시식할지, 배탈이 났을 때 어떤 케이크에 약이 들어있는지 쉽게 알 수 있습니다. 케이크 수가 늘어나도 같은 원리를 적용할 수 있습니다. 케이크가 8개일 땐 아래처럼 세 자릿수의 2진수로 표시하면 됩니다. 

케이크의 개수에 따라 2진수의 자리를 늘려가며 각 자릿수에 한 명씩 움파룸파를 배치합니다. 그러면 그 조합에 따라 효율적으로 약이 든 초코케이크를 찾을 수 있답니다! 

규칙을 일반화하면 n개의 초코케이크가 있을 때 필요한 사람 수는 log2n이고 이 방법을 쓰면 반드시 약이 든 초코케이크를 찾을 수 있으면서 설사병에 걸리는 움파룸파의 수를 최소로 할 수 있습니다. 3번 제조실에서 만든 초코케이크는 8192개니까 213이므로 딱 13명의 움파룸파만 불러오면 되겠네요. 여러분도 초코케이크가 32개 있을 때의 최소 움파룸파 수를 한번 구해보세요!

적분으로 쌓아 올린 3D 초콜릿 프린터
3D 프린터는 만들고자 하는 물체를 얇은 층으로 잘게 쪼개 쌓아 올리는 방식으로 사물을 출력합니다. 물체를 잘게 쪼개서 다시 쌓아 보는 건 앞서 살펴 본 적분의 원리라고 할 수 있죠. 그런데 이런 3D 프린터에 초콜릿을 접목한 연구가 진행 중입니다. 

박근 서울과학기술대학교 기계시스템디자인공학과 교수팀은 출력 재료가 초콜릿인 3D 프린터를 시연했습니다. 

박근 교수는 “이 기술을 응용하면 액체 금속을 사용해 전자회로를 3D 프린팅으로 출력할 수도 있다”며 3D 초콜릿 프린터의 발전 가능성에 대해 설명했습니다.