문병로 서울대학교 컴퓨터공학부 교수 |
문제는 공간을 만든다. 평지와 골짜기, 봉우리로 이루어진 공간 속에 해답들이 흩어져 있다. 알고리즘은 이런 공간에서 가장 높은 봉우리(최적의 풀이)를 찾아 나선다. 알고리즘은 공간을 여행하는 교통수단이다. 과학자·엔지니어들은 저마다의 수준에 맞는 교통수단을 설계하여 이 공간으로 내보낸다.
문제 중에는 우주보다 더 방대한 공간을 가진 것이 널렸다. 한 예로 세일즈맨이 고객들을 모두 방문하고 돌아오는 가장 짧은 경로를 찾고자 한다. 조합 최적화와 관련된 컴퓨터과학의 유명한 난제다. TSP(Travelling Salesman Problem)라 부른다. 미국의 클레이수학연구소가 21세기 7대 난제를 정하고 각각 상금 100만 달러를 걸었는데 그중 하나가 이 TSP가 속한 문제 그룹의 난이도와 관계있다.
알고리즘 |
<이미지를 클릭하시면 크게 보실 수 있습니다> |
알고리즘 훈련이 되지 않은 인력이 이 문제를 푼다면 모든 경우를 따져 가장 좋은 것을 찾을 것이다. 이런 방식으로 필자의 책상에 있는 PC를 가동하면 고객이 25명일 경우 답을 찾는 데 100억 년이 걸린다. 30명이면 20경 년 정도 걸린다. 30명짜리가 이런데 8000명짜리 문제의 최고봉을 찾아 나서는 여행을 생각해보라.
봉우리들은 골고루 흩어져 있지 않고 우주의 은하처럼 여기저기 군집을 이룬다. 군집의 수가 어마어마해서 시간을 충분히 주어도 극히 일부만 볼 수 있다. 지형도 험준하고 복잡하다. 그래서 연구자들이 같은 문제에 대해서도 코끼리 다리처럼 각자의 관점에서 보게 된다. 결국 방대한 공간을 여행하는 알고리즘은 전체 중에 턱없이 일부만 보고는 어림셈을 해야 한다. 그래서 컴퓨터과학의 대부분 난제를 푸는 기술의 핵심은 어림셈이다.
이런 식으로 풀어야 하는 문제들은 널렸다. 반도체 공장 라인에도 이런 문제가 있고, 금융투자 회사에도 있다. 지금은 대충 하고 있지만 택배 회사의 고객 할당과 스케줄링도 그런 난제다. 과학자·엔지니어는 물론이고 기업의 경영자나 임직원들은 우선 자신의 주변에 이런 문제의 존재를 감지할 수 있는 기술적 감수성을 가져야 한다. 그래야 문제를 발견하고 알고리즘을 만드는 단계로 넘어갈 수 있다. 그런 난제가 있는 곳에서 관련자들이 문제의 존재를 전혀 감지하지 못하는 경우가 흔하다. 쏟아지는 데이터는 새로운 문제를 만들고, 문제는 새로운 공간을 만든다. 무궁무진한 공간 여행의 시대가 왔다.
문병로 서울대학교 컴퓨터공학부 교수
▶ 중앙일보 '홈페이지' / '페이스북' 친구추가
▶ 이슈를 쉽게 정리해주는 '썰리'
ⓒ중앙일보(https://joongang.co.kr), 무단 전재 및 재배포 금지
이 기사의 카테고리는 언론사의 분류를 따릅니다.
기사가 속한 카테고리는 언론사가 분류합니다.
언론사는 한 기사를 두 개 이상의 카테고리로 분류할 수 있습니다.
언론사는 한 기사를 두 개 이상의 카테고리로 분류할 수 있습니다.