#0: 독서계획

알고리듬. 주어진 문제 해결을 위한 명시적 절차.

모든 인간은 이런저런 문제를 해결하며 살아간다. 그래서 '알고리듬 비전공자’라는 말은 마치 ‘보수의 품격’처럼 이율배반적이고 이상한 단어 조합이라는 생각도 든다. 그러나 여기에서 나는 알고리듬 비전공자다.

알고리듬 비전공자로 코딩을 시작한 이후 나를 괴롭힌 이슈 중 하나는 알고리듬을 공부할 분야로 보아야 하는가 였다. 프로그래밍 튜토리얼을 따라가면서는, 튜토리얼 끝나는 바로 다음날 시작해야 할 과정으로 믿기도 했다. 하지만 알고리듬은 일견 방대해 보였고, 정말 볼수록 방대했다. 

또 다행히도 지난 몇 달간 내게 코딩을 필요로 하는 문제는 알고리듬 산행을 요구하지는 않았다. CPU 연산시간이나 메모리 등 computing power 비용을 생각할 필요도 없는 것들이었다. 모로 가도 서울로만 가면 되었고, 결국 어떻게든 서울로 갈 수 있었다. 때로는 수없는 구글링이 때로는 짜릿한 직관이 날 그리로 데려다 주었다. 돌이켜 보면 각각이 나름대로 길고 고통스런 행군이었지만, 어쨌든 서울이 보이는 행군이었다.

알고리듬을 공부해야겠다고 마음먹게 된 것은 — 아니 보다 솔직히 말해서 공부할 수밖에 없다고 인정하게 된 것은, 어디서 보았는지 기억나지도 않는 심심풀이 문제 때문이다.

m쪽, n개의 챕터로 이루어진 두꺼운 책을 k일 동안 꾸준히 읽어 끝낼 수 있는 계획을 세워야 한다. 일일 독서분량은 챕터 단위로, 순서대로 짜되, 하루에 읽는 양이 최대한 균일하도록 구분해야 한다. 가령 5개 챕터가 [20쪽, 50쪽, 30쪽, 50쪽, 60쪽]으로 이루어진 210쪽의 책을 3일 동안 꾸준히 읽기 위한 최적의 배분은 [[20, 50], [30, 50], [60]]이 될 것이다. 이러한 계획 제안을 위한 알고리듬은?

따로 적어두지 않아도 기억될 만큼 간단한 이 문제는, 그러나 지금까지 내가 코딩하며 접근했던 방식으로는 원하는 결과를 보장하지 않았다. 답이 보이지도, 답을 구하는 과정을 정의하기도 어렵다. 위와 같이 5개 챕터라면 고민할 것도 없지만, [20, 34, 84, 45, 9, 96, 65, 93, 36, 53, 50, 96] 정도만 되어도 머릿속에서 잘 그려지지 않는다.

돌이켜 보면 그동안 나의 코딩은 답이 무엇인지 논리적으로든 직관적으로든 미리 알 수 있는 상태에서 이루어진 것들이었다. 즉 문제를 정의하는 과정에서 답에 이르는 절차가 머릿속 칠판에 명료하든 뿌옇든 미리 그려지고, 그것을 언어로 더듬더듬 옮기는 과정이었다. 달리 말해 지금까지의 코딩 문제들은 실제로는 번역의 문제였다.

그러나 이 문제는 일종의 철학의 문제로 느껴졌다. ‘최적’이란 무엇인가, 서울이 보이지 않는 상태에서 서울과 가장 가깝다고 생각되는 지점을 향해 갈 때 나는 어디에서 안주해도 되는가.. 이 문제는 그런 질문을 함께 던지고 있는 것처럼 느껴졌다.

물론 보기에 따라서는 그동안 내가 해왔던 것과 크게 다르지 않은 번역의 문제이기도 하다. n개의 챕터를 k일로 구분하는 모든 경우의 수를 대입해서 분산(variance)을 내어보고, 그 중 최소값을 내는 경우를 찾는 문제로 정의하면 그렇다. 소위 brute-force 방식이다.

그런데 이런 접근은 뭔가 마음에 들지 않았다 — 너무 비효율적으로 느껴졌다. 처음부터 왜 그런 느낌을 갖게 되었는지 특정하기는 어렵지만, 아마 내가 ‘손으로’ 혹은 ‘눈으로' 이 문제를 푼다면 그런 식으로 접근하지 않기 때문인 것 같다. (그것이 big-O notation 상 O(n!)에 해당하기 때문에 비효율적이라는 사실을 알게 된 건 나중의 일이다.)

그 접근이란 대략 이렇다.

1. 길이 n의 수열, 즉 n개의 숫자들을 훑어본다.

2. 이 수열을 너무 크거나 작아 보이지 않는 k개의 묶음으로 나누고, 묶음별로 더한 k개 값들에 대해 분산을 구한다.

3. 앞의 과정에서 역시 유효하다고 여겨지는 다른 묶음을 만들어 분산을 구한다.

4. 두 분산을 비교하여 값이 보다 작은 묶음을 취한다.

5. 더이상 유효하다고 생각되는 묶음이 떠오르지 않을 때까지 3-4의 과정을 반복한다.

6. 5까지 수행하는 과정에서 분산이 가장 작은 묶음을 결과로 취한다.

그런데 내가 지금껏 해온 코딩으로는 ‘너무 크거나 작아 보이지 않게’, ‘유효하다고 여겨지는’과 같은 개념을 옮길 수가 없다. 

그런데 왠지 그것을 옮길 수 있을 것만 같다.. 언젠가부터 피보나치 수열의 n번째 값을 재귀식(recurrence relation)이 아닌 닫힌 형태식(closed-form expression)으로 구할 수 있는 것처럼 말이다.

한편 이제는 그런 개념을 코딩으로 옮기는 방법을 숙지할 필요가 있어 보인다. 아니면 적어도 그것을 옮길 수 있는 방법이 존재하는지 여부는 알고 있어야 할 것 같다. 나 스스로도 바깥 세상도 코딩으로 하려는 일의 유형이 너무나 다양해져 버렸으니까.

이 문제로 2주를 끙끙거렸음에도 마땅한 길이 보이지 않았다. 그러다 나는 인류가 피보나치 수열을 생각한 이후 그 닫힌 형태식, 즉 Binet’s Formula를 발견하는 데 최소한 2000년이 걸렸다는 사실을 알게 되었다. 더이상 알고리듬 산행을 망설일 이유가 없었다.