알고리즘, 공간의 여행

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

우주에는 은하가 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명짜리 문제의 최고봉을 찾아 나서는 여행을 생각해보라.

봉우리들은 골고루 흩어져 있지 않고 우주의 은하처럼 여기저기 군집을 이룬다. 군집의 수가 어마어마해서 시간을 충분히 주어도 극히 일부만 볼 수 있다. 지형도 험준하고 복잡하다. 그래서 연구자들이 같은 문제에 대해서도 코끼리 다리처럼 각자의 관점에서 보게 된다. 결국 방대한 공간을 여행하는 알고리즘은 전체 중에 턱없이 일부만 보고는 어림셈을 해야 한다. 그래서 컴퓨터과학의 대부분 난제를 푸는 기술의 핵심은 어림셈이다.

이런 식으로 풀어야 하는 문제들은 널렸다. 반도체 공장 라인에도 이런 문제가 있고, 금융투자 회사에도 있다. 지금은 대충 하고 있지만 택배 회사의 고객 할당과 스케줄링도 그런 난제다. 과학자·엔지니어는 물론이고 기업의 경영자나 임직원들은 우선 자신의 주변에 이런 문제의 존재를 감지할 수 있는 기술적 감수성을 가져야 한다. 그래야 문제를 발견하고 알고리즘을 만드는 단계로 넘어갈 수 있다. 그런 난제가 있는 곳에서 관련자들이 문제의 존재를 전혀 감지하지 못하는 경우가 흔하다. 쏟아지는 데이터는 새로운 문제를 만들고, 문제는 새로운 공간을 만든다. 무궁무진한 공간 여행의 시대가 왔다.

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