중세 판타지에서 과학적으로 살아남기

승리의 함수(2)

10년 전, KAIST N1 빌딩. 전산학부 계산 이론 수업.

“자자, 자리에 앉게나. 다들 환영하네. ”

희끗희끗한 은발에 살짝 벗겨진 이마가 인상적인 초로의 교수님이 강의실로 들어왔다.

“오늘부터 당분간 자네들은 컴퓨터 과학 및 공학의 핵심이론이라고 할 수 있는 계산 이론, 그중에서도 ‘계산 복잡도 이론(Computational complexity theory)’의 이론과 실제에 관해 나와 같이 배워보게 될 걸세. 아, 혹시라도 첫 수업이니 일찍 마쳐주지 않겠냐는 기대를 했다면 버리도록. ”

좌중에 울려 퍼진 탄식과 함께, 교수님은 그때까진 남아있었던 앞머리를 휙 쓸어 넘기고는 수업을 시작했다.

“본 이론에서, 세상의 모든 문제들은 크게 ‘결정 문제’와 ‘함수 문제’로 나뉘네. 여기서 결정 문제란 예, 아니오로 답이 나오는 질문을 말하지. 예를 들면 ‘두 숫자 x와 y가 존재할 때 y는 x의 배수인가?’ 같은 질문이네. 그리고 이 결정 문제들을 푸는 데 쓰는 방법을 ‘알고리즘’이라고 부르지. ”

몇몇 학생들은 흥미롭게 고개를 끄덕였고, 몇몇은 이미 알고 있었다는 듯 지루하다는 표정을 지었다. 아예 관심이 없는 일부는 재수강러였을 것이다.

“한편 함수 문제란 결정 문제가 아닌, 답이 3개 이상인 문제를 의미하네. 이를 테면 ‘두 숫자 x, y가 존재할 때 x는 y의 몇 배인가?’라는 문제는 x와 y의 값에 따라 수많은 답이 나올 수 있으므로 함수 문제이지. 우리가 다룰 계산 이론에서는 일반적으로 결정 문제들만을 다룬다고 보면 되네. ”

그때 한 학생이 번쩍 손을 들고는 질문했다.

당시에만 해도 파릇파릇했던 11학번 신입생, 나였다.

“오! 벌써 질문인가? 열정이 넘치는군. 하시게. ”

“하지만 교수님. 말씀대로라면 우리들이 실제로 살면서 맞닥뜨리는 문제들은 대부분이 함수 문제 아닙니까? 예, 아니오로 딱딱 떨어지는 결정 문제만을 다루는 건 너무 범위가 좁지 않나요? 그게 의미가 있습니까? ”

다소 도전적인 어조의 질문에 교수님은 잠시 놀란 얼굴을 하더니 기쁜 듯한 웃음을 지었다.

“음! 좋은 질문이군. 계산 이론을 이제 막 접했으니 그리 생각할 수도 있겠지. 하지만 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한 부분 집합이기 때문에, 함수 문제도 결국 결정 문제로 환원될 수 있다네. 이는 알고리즘을 쓸 수 있다는 의미고 그것으로 문제를 해결할 수 있다는 얘기지. 자네도 알겠지만 아까 예로 들은 두 문제들은 본질적으로는 같은 문제야. 그리고 이런 원리는 훨씬 복잡하고 어려운 문제에도 적용될 수 있지. 예를 들어 볼까? 워낙 유명하니 다른 곳에서 주워들어 아는 사람들도 있을 걸세. 조합 최적화 문제 중에서도 가장 유명한 난제인 ‘외판원 문제’, ‘Traveling salesman problem’을 살펴보지. ”

교수님이 빔 프로젝터로 띄워두었던 PPT를 촤라락 뒤쪽으로 넘기더니 말을 이었다.

“자, 외판원인 자네들은 한정된 예산으로 여러 도시를 한 번씩 들러야만 퇴근할 수 있네. 각각의 도시들 사이에는 각자의 가중치-여기서는 이동할 때 들어가는 비용이라고 정의하겠네-가 주어져 있고, 따라서 어느 도시를 먼저 들리느냐에 따라서 총 비용이 달라지지. 원래는 모든 도시들을 한 번씩 들렀다가 시작점으로 돌아와야 하지만 편의상 돌아와야 하는 제약은 생략하겠네. 그래도 시간 복잡도(알고리즘이 문제를 해결하는데 걸리는 시간)는 변하지 않으니까. ”

강단을 한 번 쭉 둘러본 교수님이 포인터를 조작해서 비어있던 화면에 삼각형의 그림을 띄웠다.

각 변의 길이가 2:1:3인 삼각형의 꼭짓점 위에 서울과 대구, 부산이라는 익숙한 도시 이름들이 기입되어 있었다.

“가장 간단한 도시가 3개만 있는 경우를 따져 보세. 변의 길이만 봐도 알겠지만 서울과 대구 사이의 가중치가 20, 대구와 부산 사이의 가중치가 10, 부산과 서울 사이의 가중치가 30이라고 가정하지. 딱 봐도 이미 정답이 나와 있지? 서울에서 대구를 거쳐 부산으로 가거나, 부산에서 대구를 거쳐 서울로 가야하네. 이때 총 비용은 30이 되고. 어떤가? 너무 쉽지? ”

난제라고 한 것치고는 너무 간단한 해결에 학생들이 다소 맥 빠진 표정으로 고개를 끄덕였다.

“하지만 도시의 수가 조금만 늘어도 생각보다 만만치 않아진다네. 경로의 경우의 수가 n!(팩토리얼)이거든. 방금 예시에서 가능한 경로의 수는 3!, 즉 3x2x1=6(개)에 불과하지. 하지만 들러야 할 도시가 10개로 늘면 어떻게 될까? 방금 질문한 학생? 이름이 뭐지? ”

“이미르라고 합니다. ”

“그래, 미르 군. 답해보게. ”

“정확히는 모르겠지만... 300만 가지는 넘겠네요. ”

“오! 그 정도면 맞춘 걸로 치지. 정확히 3,628,800가지가 된다네. 자, 그럼 20개라면? ”

“그거는... 계산기를 가져와야 할 것 같은데요? ”

“그래! 무려 2,432,902,008,176,640,000가지나 되니까. 사실 이쯤 되면 슈퍼컴퓨터를 가져와도 정답을 구하기 어렵다네. ”

200경이라는 천문학적인 숫자에 일각에서 놀란 반응이 나오자, 교수님이 짐짓 만족스러운 표정을 지었다.

“이 문제를 보다 수학적으로 엄밀하게 정리하면, ‘그래프 상의 모든 정점들을 한 번씩 지나가는 사이클-일명 헤밀턴 순환이지- 가운데 가중치가 가장 낮은 것이 무엇인가?’라고 할 수 있겠지. 자, 슬슬 저게 뭔 소린가 싶을 거야. 묻고 싶을 걸세. ‘슈퍼컴퓨터로도 계산이 어려우면 어떻게 답을 구하라는 말이야? 여기 전산학부 강의실 아냐? 왜 시작부터 초를 쳐?’. ”

나이치고 천연덕스러운 교수님의 연기에 나를 포함한 몇몇이 피식 웃음을 터뜨렸다.

“물론 모든 경우의 수를 일일이 따져 정답을 뽑아내는 건 현실적으로 불가능하다네. 하지만 차선책이라면 존재하지. 요컨대 자네들 자신이 외판원이거나 그들을 파견하는 회사라고 생각해 보게나. 완벽한 최적은 아니더라도 ‘예산 안에 들어오는 경로’를 찾을 수 있다면 충분한 의미가 있지 않겠나? ”

되물어온 교수님이 나와 눈을 마주쳤다.

“예. 그렇습니다. ”

고개를 끄덕인 교수님이 흡족한 얼굴로 설명을 이어갔다.

“최적해에 대한 욕심만 내려놓는다면 우리들은 두 가지의 무기를 써서 근사해를 얻을 수 있다네. 첫 번째는 조금 전에 언급했던 환원(Reduction)이지. 위에서 한 가정들을 받아들인다면 본 함수 문제는 ‘그래프 상 모든 정점을 지나는 사이클 가운데 특정한 예산 이하인 것이 존재하는가?’라는 결정 문제로 환원시킬 수 있네. 어떤가? 목적이 훨씬 더 명확해졌지? 그럼 이제 두 번째 무기인 알고리즘이 출동할 시간이네. 나중에 배우겠지만 ‘풀림 기법’이나 ‘유전 알고리즘’ 등의 메타휴리스틱 기법을 사용해서 유의미한 근사해를 얻을 수 있지. ”

마침내 말을 맺은 교수님이 연단에 있던 생수를 꿀꺽꿀꺽 들이켰다.

“음, 말하다 보니 신이 나서 생각보다 설명이 길어져버렸군. 어떤가? 이미르 군. 답변이 되었나? ”

“네! 감사합니다. ”

“더 궁금한 게 있다면 내 방으로 오게. ”

10년 넘게 이어진 교수님과 내 인연의 시작이었다.

* * *

잠시 추억에 젖어 있다가 판타지 같은 현실로 돌아왔다.

아마포로 감싼 지푸라기 침대에서 뒤척이다 떠오른 생각은 지금 내 상황이 그때의 문제와 상당히 닮아있다는 것이었다.

도시를 순회하는 외판원은 아니지만, 주어진 상황 하에 가지고 있는 예산 내에서 최선의 경로를 찾아내야한다는 본질적인 목표는 같았으니까.

완전히 최적까지는 아니라도, 적어도 호손이 승리할 수 있을 만큼의 해결책을 찾아내야 한다는 점 역시 비슷했다.

그치만 어떻게?

문득 방금 떠오른 강의를 이용해보자는 생각이 들었다.

내 머리가 튜링 기계는 아니겠지만, 어쨌거나 복잡한 문제를 Yes or No의 이지선다로 정리할 수 있다면 생각을 가다듬고 해결책을 찾는 데 도움이 될 테니까.

내가 찾아야 하는 해답은 호손의 승리법.

이왕이면 희생자가 나지 않는 편이 좋고 비용도 적게 드는 편이 바람직하다.

이것을 함수 문제로 표현하면 이쯤 되겠지.

‘호손을 최소한의 희생과 비용으로 승리시키는 방법은? ’

몇 주간 나를 지긋지긋하게 괴롭혀왔던 질문.

이걸 결정 문제로 환원시키면 이렇게 되리라.

‘호손을 최소한의 희생과 비용으로 승리시키는 방법은 존재하는가? ’

그리고 그 답이 O라는 것을 나는 신탁을 통해 알고 있다.

그렇다면 내가 찾아야 하는 것은 답 자체가 아니라, 그 답으로 나를 이끌어줄 ‘알고리즘’이다.

알고리즘(algorism).

컴퓨터 시대가 온 이후로 거의 컴퓨터 과학 용어처럼 정착된 이 말은 원래 문제를 해결하기 위한 일련의 절차를 의미한다.

컴퓨터 프로그램도 정교한 알고리즘들의 집합이고 3x2=6 같은 간단한 산수 역시 알고리즘이다.

알게 모르게 우리는 알고리즘의 홍수 속에서 그것을 쓰며 살아가고 있다.

이곳에서의 나 역시 다르지 않다.

‘내가 지금까지 써온 알고리즘은... ’

‘언덕 오르기(Hill climbing)’.

말 그대로 가장 높은 곳(목표)에 오르기 위해 현재 위치에서 더 높은 언덕이 보이는 방향으로 걸어가는 방법이다.

비유를 걷어내고 말하면 한 단계의 선택이 이전 단계의 상태보다 나은지를 평가해서 나을 경우 그쪽으로 향한다.

대부분의 사람들이 부지불식간에 쓰고 있는 평범하고 당연한 방법이었다.

점점 높은 곳으로 향하다 보면 언젠가 정상에 닿는다.

등산과 다를 바 없는 너무나도 당연한 이치.

하지만 이 알고리즘에는 치명적인 단점이 있다.

바로 극대점(local maximum)과 최대점(global maximum) 문제였다.

극대점이란 주변에 더 높은 장소들이 보이지 않는 지역의 고점을 뜻하고, 최대점은 전체에서 가장 높은 곳, 즉 최적의 해답을 의미한다.

언덕 오르기 알고리즘의 가장 큰 단점은 한정된 시간과 시야 속에서 최대점을 찾지 못하고 극대점에 갇혀버릴 가능성이 있다는 것이다.

저 너머에 훨씬 높은 꼭대기가 있는데 거리가 멀어서 보이지 않는다면?

날카로운 능선 위에 있어 동서남북 어디로 가도 고도가 낮아지는데 내려갔다가 다시 오를 시간이 부족하다면?

평평한 고원 위에서 어디로 가야할지 판단이 서지 않는다면?

결국 가까운 봉우리의 꼭대기에서 멈출 수밖에 없고, 거기가 세상 꼭대기는 아닐지언정 목표 달성에는 충분한 높은 지점인지 딴에는 높은 줄 알았는데 사실은 어림도 없는 얕은 둔덕인지는 알 수가 없는 것이다.

나는 여태까지 꽤 잘 해 왔다고 생각한다.

괴철로 대신에 고로를, 신명재판을 피하는 대신에 정면 돌파를, 삼포제 대신에 3윤작법을.

그때그때 주어지는 선택지에서 언제나 더 나은 쪽을 보며 걸어왔고 옳은 선택을 해 왔다고 자부한다.

하지만 그걸로 충분할까?

꾸역꾸역 올라가는 것처럼 보여도 목표달성은 불가능한 아래 지역의 극대값에서 끝끝내 멈추게 되는 것은 아닐까?

한 달 전 체결한 대출계약에서 앤더슨 상단은 자신들의 속셈이 자철석 광산임을 숨기고자 어업권을 굳이 조항에 넣었다.

그리고 이쪽은 그것을 간파하고도 그들을 역이용할 생각으로 기꺼이 받아들여 저들을 안심시켰다.

당시로서는 최선의 선택, 더 높은 봉우리였다.

그런데 지금은 바로 그 선택이 부메랑이 되어 호손의 식량난과 물자난을 유발하고 있었다.

이 언덕만 넘으면 더 높은 봉우리가 보일 줄 알았는데, 오히려 쭉 미끄러져 안개 속을 헤매고 있는 형국이다.

그나마 감자와 윤작법으로 다시 오르막을 오르고 있지만, 같은 일이 다시 일어나지 말라는 법이 있을까?

그것이 최근 나를 괴롭혀온 불안감의 정체였음을, 나는 비로소 직시했다.

그렇다면,

‘알고리즘을 바꿔야지. ’

판을 뒤엎을 때였다.

10년 전에 교수님이 가르쳐주시고 내가 배웠던 방식으로.

‘봉우리’는 뒤집히는 순간 거꾸로 ‘바닥’이 되니까.

[탈지제]

오늘자 요약: 주인공이 이세계로 끌려오게 된 이유-교수: 이학생... 내 랩실에서는 어떨까? 를 느끼게 만들도록 교수님을 도발함

[ha******]

잼 있어요. 어렵네요.

[MecheMec..]

교수: ㅋㅋㅋㅋ 호박이 덩굴째 들어오네?

[화이트캐롤]

언제나 기대를 저버리지 않는, 신뢰할 수밖에 없는 글이네요.
적절하며 넘치는 예시와 비유, 그 사이를 메꾸고 이끌어 나가는 작가님의 유려한 글솜씨에 늘 감탄합니다~~~
좋으신 글, 다시한번 감사드립니다~~