가장 빠른 사람이 횃불을 나르면 오히려 손해 보는 다리
속도가 다른 네 사람, 횃불은 하나, 다리는 2인용. 모두 건너는 데 최소 몇 분일까?
다리의 답은 빠른 발이 아니라 느린 발의 배치다
Experiment
직접 만져보기
🌉 바로 도전! 걸음이 1·2·5·10분인 네 사람을 모두 건너편으로 보내세요. 다리는 한 번에 두 명까지, 건너려면 🔥횃불이 필요합니다. 둘이 가면 느린 쪽의 시간이 걸려요.
이쪽 강가🔥 횃불
건너편
📖 더 읽기 — 왜 필요한가 · 인사이트 · 흔한 오해 · 수식 정리펼치기 ▾
Why
왜 필요한가
밤길에 네 사람이 낡은 다리 앞에 섰습니다. 다리는 한 번에 두 명까지, 횃불 없이는 건널 수 없어요. 네 사람의 걸음은 1분·2분·5분·10분으로 제각각입니다. IT 기업 면접 문제로도 유명해진 고전 퍼즐이에요.
누구나 처음엔 같은 답을 냅니다. '가장 빠른 1분이 횃불을 들고 왕복하면 되지.' 그렇게 하면 19분이 걸려요. 그런데 이 문제의 진짜 답은 17분입니다. 빠른 사람을 더 굴려서가 아니라, 느린 두 사람을 함께 보내서 얻는 2분이에요.
가장 좋은 배치를 찾는 수학을 최적화라고 부릅니다. 배달 경로, 공장 일정, 비행기 시간표가 전부 이 질문 위에 서 있어요. 이 다리가 그 세계의 입구입니다.
Insight
영상에서 말한 인사이트
“비싼 비용은 한 번만 낸다.”
10분짜리 횡단은 피할 수 없는 비용입니다. 최선의 전략은 그 10분 속에 5분을 숨기는 것이에요. 큰 비용을 낼 때 다른 비용을 같이 처리하면, 작은 비용은 사라진 것과 같습니다.
“직관의 답과 최선의 답 사이에 최적화가 있다.”
19분도 꽤 그럴듯한 답입니다. 하지만 '더 줄일 수 없나?'라고 한 번 더 묻는 순간 2분이 나와요. 그 한 번의 질문이 최적화라는 수학의 시작입니다.
Misconception
사람들이 흔히 하는 오해
가장 빠른 사람이 횃불을 도맡는 것이 언제나 최선이다.
느린 두 사람을 함께 보내면 10분을 내는 동안 5분이 공짜로 따라옵니다. 돌아오는 값이 조금 비싸져도 아낀 5분이 더 커요. 이 문제에서는 19분이 17분으로 줄어듭니다.
경우가 몇 개 안 되니 아무렇게나 해도 금방 최선이 나온다.
왕복 순서까지 세면 경우는 수십 가지가 넘습니다. 사람이 다섯, 여섯으로 늘면 경우는 폭발해요. 그래서 '느린 것끼리 묶는다' 같은 원리를 찾는 쪽이 하나하나 세는 것보다 강합니다.
Formula
수식으로 정리하기
전략을 식으로 적어 보면 두 답의 차이가 한눈에 보입니다. 빠른 사람이 왕복하는 A안과 느린 둘을 묶는 B안. 달라지는 것은 가운데 한 수뿐이에요.
🔬 공식 해부 — 17분 전략의 다섯 걸음
+ + + + = 17
직관의 답 — 빠른 발 왕복
1분이 횃불을 도맡아 한 명씩 실어 나릅니다. 5와 10을 따로따로 다 내는 것이 약점이에요.
최선의 답 — 느린 발 묶기
5와 10을 함께 보내 10분만 냅니다. 돌아오는 값이 1에서 2로 비싸져도, 아낀 5분이 더 커서 이겨요.
묶기가 이기는 조건
a·b가 빠른 둘, c가 셋째로 느린 사람일 때. 둘째 b의 왕복 값이 a와 c의 합보다 싸면 묶기가 이깁니다. 이 문제는 4 < 6이라 묶기의 승리예요.
In Real Life
현실에서 만나는 곳
배달 라이더의 묶음 배송
같은 아파트로 가는 주문 두 개를 한 번에 들고 갑니다. 먼 길이라는 큰 비용을 한 번만 내는 다리의 전략과 같아요.
오븐의 일괄 굽기
오븐을 한 번 달굴 때 빵을 가득 채워 굽습니다. 예열이라는 비싼 비용을 여러 빵이 나눠 내는 것이죠.
비행기 허브 공항
장거리 노선 하나에 승객을 모아 태우고, 도착해서 짧은 노선으로 흩어집니다. 비싼 횡단을 한 번만 내도록 설계된 하늘길이에요.
컴퓨터의 작업 스케줄링
컴퓨터도 '비용 큰 일을 언제, 무엇과 함께 처리할까'를 계산합니다. 다리 문제는 스케줄링 이론의 축소판이에요.
Practice
풀어보기 — 유형 정복
✏️ 유형별 문제 4개 — 스스로 풀어 정복하기탭해서 문제 풀기 ▾
1·2·5·10분 네 사람이 2인용 다리를 건너는 최단 시간은?
17분 전략의 핵심 한 수는 무엇일까요?
걸음이 1·2·6·8분인 네 사람이라면 최단 시간은 몇 분일까요?
빠른 사람이 횃불을 도맡는 왕복 작전은…
Watch
관련 유튜브 영상
Connection
개념은 이어진다
이전 개념
다음 개념으로 연결
Related
함께 보면 좋은 실험실
관련 실험실
관련 실험실