preLoad Image preLoad Image
검색 바로가기
주메뉴 바로가기
주요 기사 바로가기
다른 기사, 광고영역 바로가기
중앙일보 사이트맵 바로가기

[문병로의 알고리즘 여행] 알고리즘, 공간의 여행

문병로 서울대학교 컴퓨터공학부 교수

문병로 서울대학교 컴퓨터공학부 교수

우주에는 은하가 1000억 개 정도 있고, 각각의 은하는 평균 1000억 개씩의 항성을 갖고 있다. 그러니 우주에는 1조의 100억배 남짓한 항성이 있다. 우리는 1000억 개의 은하 중 하나에 불과한 은하수에 속해 있다. 은하수에는 4000억 개의 항성이 있는데 지구는 은하수 중심에서 빛의 속도로 2만8000년 걸리는 변두리 항성인 태양에 붙은 혹이다. 신이 이 보잘것없는 지구에 있는 인간을 우주의 주인공으로 설계했다는 믿음은 여간 무모하지 않고는 갖기 힘들다.
 
문제는 공간을 만든다. 평지와 골짜기, 봉우리로 이루어진 공간 속에 해답들이 흩어져 있다. 알고리즘은 이런 공간에서 가장 높은 봉우리(최적의 풀이)를 찾아 나선다. 알고리즘은 공간을 여행하는 교통수단이다. 과학자·엔지니어들은 저마다의 수준에 맞는 교통수단을 설계하여 이 공간으로 내보낸다.
 
문제 중에는 우주보다 더 방대한 공간을 가진 것이 널렸다. 한 예로 세일즈맨이 고객들을 모두 방문하고 돌아오는 가장 짧은 경로를 찾고자 한다. 조합 최적화와 관련된 컴퓨터과학의 유명한 난제다. TSP(Travelling Salesman Problem)라 부른다. 미국의 클레이수학연구소가 21세기 7대 난제를 정하고 각각 상금 100만 달러를 걸었는데 그중 하나가 이 TSP가 속한 문제 그룹의 난이도와 관계있다.
 
알고리즘

알고리즘

가정에 따라 달라지지만 고객이 20명이면 TSP가 만드는 공간에는 봉우리가 평균 170개 정도 있다. 170개의 봉우리 중 가장 높은 것을 찾으면 된다. 쉽다. 고객이 100명이면 봉우리는 3경4000조 개 정도로 늘어난다. 폭발적인 증가 속도다. 3경4000조 개의 태양이 있는 우주와 견줄 만하다. 어려워 보이지만 이 정도는 쉽게 최고봉을 찾는다. 100명짜리 문제가 이런데 고객이 1000명으로 늘면 상상을 초월하는 크기가 된다. 30여 년 전만 해도 이 정도는 감당 불가능한 문제였지만 요즘은 그리 어렵지 않게 최고봉을 찾아낸다.
 
알고리즘 훈련이 되지 않은 인력이 이 문제를 푼다면 모든 경우를 따져 가장 좋은 것을 찾을 것이다. 이런 방식으로 필자의 책상에 있는 PC를 가동하면 고객이 25명일 경우 답을 찾는 데 100억 년이 걸린다. 30명이면 20경 년 정도 걸린다. 30명짜리가 이런데 8000명짜리 문제의 최고봉을 찾아 나서는 여행을 생각해보라.
 
봉우리들은 골고루 흩어져 있지 않고 우주의 은하처럼 여기저기 군집을 이룬다. 군집의 수가 어마어마해서 시간을 충분히 주어도 극히 일부만 볼 수 있다. 지형도 험준하고 복잡하다. 그래서 연구자들이 같은 문제에 대해서도 코끼리 다리처럼 각자의 관점에서 보게 된다. 결국 방대한 공간을 여행하는 알고리즘은 전체 중에 턱없이 일부만 보고는 어림셈을 해야 한다. 그래서 컴퓨터과학의 대부분 난제를 푸는 기술의 핵심은 어림셈이다.
 
이런 식으로 풀어야 하는 문제들은 널렸다. 반도체 공장 라인에도 이런 문제가 있고, 금융투자 회사에도 있다. 지금은 대충 하고 있지만 택배 회사의 고객 할당과 스케줄링도 그런 난제다. 과학자·엔지니어는 물론이고 기업의 경영자나 임직원들은 우선 자신의 주변에 이런 문제의 존재를 감지할 수 있는 기술적 감수성을 가져야 한다. 그래야 문제를 발견하고 알고리즘을 만드는 단계로 넘어갈 수 있다. 그런 난제가 있는 곳에서 관련자들이 문제의 존재를 전혀 감지하지 못하는 경우가 흔하다. 쏟아지는 데이터는 새로운 문제를 만들고, 문제는 새로운 공간을 만든다. 무궁무진한 공간 여행의 시대가 왔다.
 
문병로 서울대학교 컴퓨터공학부 교수
AD
온라인 구독신청 지면 구독신청

중앙일보 핫 클릭

PHOTO & VIDEO

shpping&life

뉴스레터 보기

김민석의 Mr. 밀리터리 군사안보연구소

군사안보연구소는 중앙일보의 군사안보분야 전문 연구기관입니다.
군사안보연구소는 2016년 10월 1일 중앙일보 홈페이지 조인스(https://news.joins.com)에 문을 연 ‘김민석의 Mr. 밀리터리’(https://news.joins.com/mm)를 운영하며 디지털 환경에 특화된 군사ㆍ안보ㆍ무기에 관한 콘텐트를 만들고 있습니다.

연구소 사람들
김민석 소장 : kimseok@joongang.co.kr (02-751-5511)
국방연구원 전력발전연구부ㆍ군비통제센터를 거쳐 1994년 중앙일보에 입사한 국내 첫 군사전문기자다. 국방부를 출입한 뒤 최장수 국방부 대변인(2010~2016년)으로 활동했다. 현재는 군사안보전문기자 겸 논설위원으로 한반도 군사와 안보문제를 깊게 파헤치는 글을 쓰고 있다.

박용한 연구위원 : park.yonghan@joongang.co.kr (02-751-5516)
‘북한의 급변사태와 안정화 전략’을 주제로 북한학 박사를 받았다. 국방연구원 안보전략연구센터ㆍ군사기획연구센터와 고려대학교 아세아문제연구소 북한연구센터에서 군사ㆍ안보ㆍ북한을 연구했다. 2016년부터는 중앙일보에서 군사ㆍ안보 분야 취재를 한다.