한국의 모든 술집, 걸어서 한 바퀴? 美 수학자가 ‘최단 경로’ 계산 작성일 04-21 164 목록 <div id="layerTranslateNotice" style="display:none;"></div> <strong class="summary_view" data-translation="true">8만여 곳 가는 데 178일 소요<br>경찰청 ‘술집 위치정보’ 데이터<br>컴퓨터 여러 대를 병렬로 연결<br>44년 걸리는 계산 3개월에 끝내</strong> <div class="article_view" data-translation-body="true" data-tiara-layer="article_body" data-tiara-action-name="본문이미지확대_클릭"> <section dmcf-sid="zie8HMiB7S"> <figure class="figure_frm origin_fig" contents-hash="5f7273648271c9aef68564ced7b27c090a86020cc8b83ef4b80b00e21d072f95" dmcf-pid="qnd6XRnbUl" dmcf-ptype="figure"> <p class="link_figure"><img alt="윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 사진은 쿡 교수의 연구에 따른 최단 거리 경로를 나타낸다. 윌리엄 쿡 교수 제공" class="thumb_g_article" data-org-src="https://t1.daumcdn.net/news/202504/21/donga/20250421030710331xfxa.jpg" data-org-width="800" dmcf-mid="7txVWPe7zv" dmcf-mtype="image" height="auto" src="https://img1.daumcdn.net/thumb/R658x0.q70/?fname=https://t1.daumcdn.net/news/202504/21/donga/20250421030710331xfxa.jpg" width="658"></p> <figcaption class="txt_caption default_figure"> 윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 사진은 쿡 교수의 연구에 따른 최단 거리 경로를 나타낸다. 윌리엄 쿡 교수 제공 </figcaption> </figure> <div contents-hash="db317ef6d8a72aec26be7577cc2d2d418d59c9dd16bcc2f8ae1c2f1cf8b36faa" dmcf-pid="BLJPZeLK0h" dmcf-ptype="general"> 미국 유명 수학자가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 쉬지 않고 모든 술집을 걸어서 방문하면 178일 1시간 56분 17초가 걸린다. </div> <p contents-hash="75d16c6e74d9b87a5fbd9cab737f4ba0f4e58aebefedf6403a8f2cee707ffd28" dmcf-pid="b427IK413C" dmcf-ptype="general">윌리엄 쿡 캐나다 워털루대 수학과 교수는 이달 8일(현지 시간) 모든 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 계산하고 증명한 결과를 자신의 홈페이지에 공개했다. 쿡 교수는 조합론과 최적화 분야에서 세계적인 수학자다. </p> <p contents-hash="3a51da21fda1711889b7b34d28beb62f9077ec636b9e174fd5b7651f752fc6ec" dmcf-pid="K8VzC98tFI" dmcf-ptype="general">쿡 교수는 ‘외판원 문제(TSP)’라고 불리는 유명한 수학 문제를 도로에서 최적의 경로를 찾는 문제에 적용했다. 외판원 문제란 도시가 여러 개 있을 때 외판원이 모든 도시를 한 번만 지나가면서 전부 방문할 수 있는 가장 짧은 거리를 구하는 문제다. 방문하는 도시의 수가 같더라도 각 도시를 연결하는 경로가 다르고 가장 짧은 거리를 찾아야 하기 때문에 무엇을 대상으로 하느냐에 따라 완전히 다른 문제가 된다. </p> <p contents-hash="003c8ffa5ae84dafec139dca0dc31a484522c036930f56803789ae87b5daf310" dmcf-pid="96fqh26FUO" dmcf-ptype="general">쿡 교수는 엄상일 기초과학연구원(IBS) 이산수학그룹 CI(Chief Investigator)로부터 제공받은 한국 경찰청의 ‘전국 술집 위치정보’를 이용했다. 주소, 위도, 경도 등이 포함된 전국 술집 위치정보에 따르면 2023년 기준 한국의 술집은 9만680개다. 쿡 교수는 같은 건물에 있는 여러 술집은 1개의 술집이라고 설정하는 등 데이터를 정리해 술집 수를 8만1998개로 설정했다.</p> <p contents-hash="91f87eac1de141b8f44d27a5511a780361ab7c642cbcf387187159ef511e9c9c" dmcf-pid="2P4BlVP3Us" dmcf-ptype="general">쿡 교수는 술집 8만1998개를 이용해 술집 2개씩을 붙여 한 쌍을 만드는 작업을 했다. 술집은 중복으로 등장할 수 있다. 총 33억6179만5003개 쌍이 나왔다. 쿡 교수는 최단 거리를 계산해 주는 공개 시스템인 ‘오픈소스라우팅 머신(OSRM)’을 이용해 각 쌍에 묶인 2개 술집을 서로 걸어서 잇는 최단 거리를 계산했다.</p> <p contents-hash="cf875211b92867f23df43775ee08a846272ce3316f2b3b50ac1ea4f3513a879b" dmcf-pid="VQ8bSfQ0Fm" dmcf-ptype="general">쿡 교수는 방대한 최단 거리 데이터를 조합해 ‘분기한정법(branch and bound)’으로 최적의 경로를 찾아냈다. 분기한정법이란 최적의 답이 될 만한 후보를 나뭇가지처럼 늘어놓고 답이 될 가망이 없는 것들은 가차 없이 잘라버리는 방법이다. 답이 나올 수 있는 범위를 정해두고 범위를 벗어나는 값들을 지워 계산의 양을 줄일 수 있다.</p> <p contents-hash="48ab6d1cff02a79fe6c760c986f1509e6442d793e7435c0f79734f36da29a61c" dmcf-pid="fx6Kv4xp7r" dmcf-ptype="general">쿡 교수는 3개월에 걸쳐 여러 대의 컴퓨터를 병렬로 이용해 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 찾아냈다. 병렬로 연결된 각 컴퓨터가 문제를 푸는 데 사용한 시간을 모두 합하면 총 44년이다. 결과에 따르면 최단 경로에 소요되는 시간은 178일 1시간 56분 17초다. 연구 논문은 연말에 나올 예정이다.</p> <p contents-hash="318ec2ce5eefa54567bf68bcf59d5bce756cc6ae2d5f51c27709d1979a6ce1d2" dmcf-pid="4MP9T8MUpw" dmcf-ptype="general">쿡 교수는 “이번 문제를 2121개의 하위 문제로 바꿔 계산하는 양을 줄이는 수학적 아이디어로 해결했다”며 “외판원 문제를 길에서 여러 장소를 방문하는 최단 경로를 찾는 문제에 적용한 사례 중 가장 많은 수의 장소를 계산한 것”이라고 말했다. 직전 최고 기록은 2021년 네덜란드의 5만7912개 기념물을 방문하는 연구 결과다.</p> <p contents-hash="5c16f6dc2c3b70d6569e62ed6f1f8afd609fbb35ee758ffdac7e426e988249cb" dmcf-pid="8RQ2y6Ru3D" dmcf-ptype="general">쿡 교수는 “한국 경찰청이 제공하는 데이터가 정확하고 방대해 한국 술집 정보를 이용하게 됐다”고 말했다. 쿡 교수는 지난해 IBS 방문을 앞두고 한국 학생들을 위한 강연을 준비하면서 이번 문제에 도전하기 시작했다. 엄 CI는 “술집 위치정보를 구매한 가격은 단돈 1000원”이라며 “저렴한 가격으로 훌륭한 수학 결과가 나오는 데 일조해 뿌듯하다”고 했다.</p> <p contents-hash="3f636746a4ea1f69d2cbe7248c25fb8b4d5a32b61cdbeb616c8d3507a8d5a0d4" dmcf-pid="6JR4GxJq0E" dmcf-ptype="general">외판원 문제는 수학 문제이지만 실생활을 비롯해 산업계 전반에 적용되고 있다. 택배 물품을 전달하는 최적의 경로, 반도체 기판을 만드는 방법 등에 외판원 문제가 사용된다. 엄 CI는 “외판원 문제를 우주의 수많은 별을 방문하는 최단 경로를 계산하는 데도 적용할 수 있다”며 “외판원 문제에서 방문 대상 숫자를 높이면 최적화를 할 수 있는 새로운 수학적 아이디어를 생각해 낼 수 있다는 의미가 있다”고 말했다.</p> <p contents-hash="f937d9158bc5bd3530ea78aeb07607e7beac7be1ecaf74b1d55db497fb00ba93" dmcf-pid="Pie8HMiBUk" dmcf-ptype="general">이채린 동아사이언스 기자 rini113@donga.com </p> </section> </div> <p class="" data-translation="true">Copyright © 동아일보. 무단전재 및 재배포 금지.</p> 관련자료 이전 문소리 "'폭싹 속았수다', 딸이 결혼할 때 또 보고 싶은 작품이겠죠" 04-21 다음 “추격자 전략 쓰니 혁신 못 나와… 대체불가 기술 위해 집중 투자를” 04-21 댓글 0 등록된 댓글이 없습니다. 로그인한 회원만 댓글 등록이 가능합니다.
