분할정복 (divide and conquer)

너, 두 자리 수 곱셈은 암산으로 하지. 그런데 누가 갑자기 칠백삼십이 곱하기 사백구십팔을 종이도 없이 풀어 보라 하면 머릿속이 하얘진다. 너무 큰 한 덩어리라 손댈 곳이 안 보이는 거다. 그럴 때 사람은 본능적으로 이렇게 한다. 일단 한 수를 칠백과 삼십이로 가른다. 그러면 끔찍하던 한 번의 곱셈이, 만만한 여러 번의 작은 곱셈으로 흩어진다. 작은 것들을 따로 풀어 마지막에 자릿수 맞춰 더하면 끝이다. 누가 가르쳐 준 적도 없는데 너는 지금, 큰 적을 통째로 상대하지 않고 잘게 갈라 하나씩 해치우는 아주 오래된 전략을 쓴 거다. 오늘 이야기는, 이 당연해 보이는 가르기가 한 젊은이의 손에서 어떻게 수학자들의 이백 년 묵은 확신을 일주일 만에 박살 냈는가에 관한 거다.

이름부터 보자. 원래 이 말은 셈법이 아니라 권력의 언어였다. 라틴어 디비데 에트 임페라, 분열시켜 지배하라. 적이 똘똘 뭉쳐 있으면 못 이기지만, 저들끼리 갈라 놓으면 하나씩 꺾을 수 있다는 통치의 격언이다. 흥미롭게도 이 문구는 고대 로마의 어느 문헌에도 그대로 나오지 않는다. 후대 사람들이 필리포스 2세부터 카이사르까지 옛 권력자들의 수법을 묘사하느라 붙인 말이고, 르네상스의 마키아벨리가 군주에게 백성을 갈라 다스리라 조언하며 다시 불러냈다. 영어로 갈라서 정복하라는 표현이 굳은 건 대략 1600년 무렵이다. 사람을 가르던 이 차가운 말이 수백 년 뒤 문제를 가르는 따뜻한 도구로 옷을 갈아입을 줄은 아무도 몰랐다.

그 옷이 갈아입혀진 결정적 장면이 1960년 가을 모스크바에 있다. 당시 소련 수학의 황제는 안드레이 콜모고로프였다. 확률론의 기초를 새로 놓은 거인이지. 그가 대학에서 계산의 복잡성을 다루는 세미나를 열고 한 가지 확신을 못 박았다. 두 개의 n자리 수를 곱하는 데에는, 우리가 초등학교에서 배운 그 자릿수끼리 일일이 곱해 더하는 방식이 가장 빠르며 — 곧 n의 제곱에 비례하는 연산을 피할 길이 본질적으로 없다는 것이었다. 거인의 입에서 나온 말이라 아무도 토를 달지 않았다.

그런데 그 자리에 스물세 살 학생 아나톨리 카라추바가 앉아 있었다. 그는 거인의 확신을 받아들이는 대신 곱셈을 가르기 시작했다. 큰 수 둘을 각각 앞 절반과 뒤 절반으로 쪼개면, 정직하게 따져 작은 곱셈 네 번이 필요해 보인다. 그렇게 해선 빨라지지 않는다. 카라추바의 묘수는, 영리하게 더하고 빼는 곁수를 두면 그 네 번을 단 세 번으로 줄일 수 있음을 알아챈 데 있었다. 한 번을 아끼는 게 뭐 그리 대수냐 싶지만, 그 세 조각을 또 절반으로 가르고, 그 조각을 또 가르고 — 가르기가 자기 자신을 거듭 부르며 내려가면, 아낀 한 번이 눈덩이처럼 불어 전체 계산량의 차원 자체가 내려앉는다. 그는 이걸 세미나가 열린 지 채 일주일도 안 되어 해냈다. 거인이 못을 박은 그 확신을, 가장 어린 청중이 부순 것이다.

뒷이야기가 묘하다. 콜모고로프는 화를 내기는커녕 크게 흥분했다. 자기 확신이 깨진 그 결과를 다음 세미나에서 손수 알리고는 세미나를 그것으로 끝내 버렸고, 이후 세계 곳곳의 학회를 돌며 이 어린 제자의 발견을 자랑하듯 강연하고 다녔다. 그리고 1962년, 이 방법을 소련 과학원 회보에 논문으로 실어 세상에 내놓았다. 전해지기로는, 정작 카라추바 본인은 자기 결과가 그렇게 활자로 박혀 발표된 것을 한참 지나서야 알게 되었다고 한다. 진정한 거인은 제 권위가 무너지는 자리에서 박수를 친다는 걸, 이 일화가 보여 준다.

이 가르기의 발상은 카라추바 한 사람에서 멈추지 않고 거듭 더 영리하게 자랐다. 곧 곱셈을 셋이 아니라 더 잘게 갈라 더 빨라지는 방법들이 줄을 이었고, 마침내 신호를 잘게 분해해 곱셈을 돌리는 고속 푸리에 변환이라는 기법까지 이 핏줄에서 뻗어 나왔다. 오늘날 네 컴퓨터가 천문학적 자릿수의 수를 눈 깜짝할 새 곱하고, 검색 정렬을 순식간에 해내고, 거대한 화면을 매끄럽게 그려 내는 그 밑바닥에는 거의 예외 없이 이 분할정복이 깔려 있다. 거인의 확신을 깬 한 학생의 가르기가, 디지털 세계가 빠르게 돌아가게 하는 엔진의 한 축이 된 것이다.

그러니 너가 도무지 손댈 엄두가 안 나는 거대한 한 덩어리를 만나거든 — 그게 막막한 사업 계획이든, 끝이 안 보이는 프로젝트든 — 그 통짜를 노려보며 한숨 쉬지 마라. 콜모고로프의 확신을 깬 그 학생처럼 물어라. 이걸 서로 따로 풀 수 있는 작은 조각들로 어떻게 가를까. 큰 적은 정면으로 못 이긴다. 갈라 놓고, 하나씩, 그리고 마지막에 합쳐라.