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