d라이브러리

#1 미국 뉴욕에는 고등학교에 진학하려는 지원자가 8만 명에 이른다. 이들이 700개 이상의 고등학교 교육과정에 지원한다(고등학교가 아니라 교육과정이다. 1개 학교가 여러 교육과정을 개설한다). 한 사람이 12순위까지 지원 학교를 적어 낼 수 있다. 당신이 선량한 뉴욕시의 교육행정 담당자라고 해보자. 모두가 만족스럽게 학생을 배정하고 싶다. 그런데 책상 위에 산더미처럼 쌓인 지원서는 너무했다. 한숨짓지 않을 수가 있을까? 과연 어떻게 해야 학생도 최대한 만족하고 학교도 최대한 만족스럽게 학생을 받을 수 있을까. #2 의대를 졸업하고 나면 수련의 과정에 들어간다. 미국에서는 2009년 기준으로 2만9000명 이상의 학생이 병원에 지원한다. 이번에 당신은 미국의 의료 행정가다. 병원도 만족스러운 수련의를 뽑고 수련의도 원하는 병원에 들어가게 하려면 도대체 어떤 마법을 부려야 할까.

사이언스북스와 KAIST, 동아사이언스가 함께 주최한 수학 강연 시리즈 KAIST 명강4-‘수학으로 IT 세상을 풀어라’ 제7강 강의 도중에 나온 사례다. 엄상일 KAIST 수리과학과 교수가 이산수학의 최적화 문제를 설명하기 위해 실제 예를 소개했다.

잘 보면 이들 문제에는 공통점이 있다. 두 그룹이 있고, 그 그룹의 구성원들은 각각 상대 그룹의 구성원과 하나의 ‘관계’를 맺어야 한다. 각자가 선호하는 대상은 모두 다르다. 이들의 선호를 모두 고려해 최대한 모두가 만족스럽게 짝을 짓는 게 관건이다. 어디서 많이 보던 것 같다. ‘짝’ 같은 프로그램에서 하던 남녀의 짝짓기 문제와 똑같다!

규모가 작다고 해서 손쉽지는 않다. 당장 일고여덟 명이 둘러앉은 테이블 위에서의 짝을 한번 지어 보라. 가장 마음에 드는 사람부터 1순위, 2순위, 3순위, … 이렇게 정해 놨는데, 다른 경쟁자들은 물론 상대방의 ‘사랑의 화살표’가 어디로 향하는지 알 수 없다. 선호를 모두 고려해 가며 두 명씩 ‘최적의’ 짝을 이루는 일은 생각보다 훨씬 어렵다.

일상생활에서 ‘짝’을 지을 일은 꽤 많다. 그런데 이를 잘 지으려면 수학이 필요하다. 게일-샤플리 방법이라는 알고리듬은 오로지 이런 짝을 잘 지우는 방법을 찾기 위해 개발됐고, 이 방법을 제안한 수학자들은 나중에 노벨상까지 탔다. 의료, 교육 등 각종 지원자 시스템이 지금처럼 잘 굴러갈 수 있는 것도 이들 덕분이다.

짝짓기가 지원자와 병원, 지원자와 학교 사이를 최적화하고 있을 때, 공간의 최적화 문제를 해결한 수학 이론도 있다. 흔히 ‘외판원 문제’라고 불리는 이 문제는, 공간에 흩어진 여러 점을 최소한의 노력으로 모두 거치는 방법을 연구한다.

세계지도를 펼쳐놓고 지금까지 세워진 스타벅스 매장을 모두 방문하는 계획을 세워보자. 스타벅스코리아 홈페이지에 따르면 스타벅스의 전세계 매장 수는 1만7000개가 넘는다. 그냥 날아다니기엔 비행기값도 비싸고, 무엇보다 여기저기 하릴없이 헤매기엔 인생이 너무 짧다. 가장 효율적으로 돌아다닐 방법을 찾고자 할 때, 외판원 문제 해결책은 큰 도움이 된다. 반도체 기판을 만들 때, 아마존 사에서 택배 물품을 관리할 때, 하다못해 마트에서 장을 볼 동선을 세울 때도 도움이 된다. 컴퓨터의 도움으로 지금까지 무려 8만5900개의 점을 연결하는 최적 경로까지 풀었다고 하니, 스타벅스 매장 방문 순서쯤이야 식은죽 먹기겠다. 그런데 아무리 최적 경로를 안다 해도, 과연 죽기 전에 다 방문할 수 있을까.