퇴근길, 네비게이션이 두 가지 경로를 제안한다.
경로 A: 35분. 고속도로를 타고 크게 돌아간다.
경로 B: 25분. 이면도로를 빠져나가는 최단 거리.
당연히 B를 누른다. 10분이나 빠르잖아. 그런데 이면도로에 진입하자마자 정체가 시작된다. 신호마다 걸린다. 좁은 골목에서 마주 오는 차와 눈싸움을 한다. 25분이 40분이 되고, 50분이 된다. 고속도로를 탔으면 진작에 집이었다.
지금 이 순간 가장 좋아 보이는 선택이, 전체로 보면 최악이었다.
이 함정에는 이름이 있다. 컴퓨터 과학에서는 이것을 탐욕 알고리즘(Greedy Algorithm)의 한계라고 부른다.
탐욕 알고리즘의 원리는 단순하다. 매 단계에서, 그 순간 가장 좋아 보이는 것을 선택한다. 미래는 고려하지 않는다. 지금 눈앞의 최선만 취한다.
놀라운 것은, 이 단순한 전략이 꽤 많은 문제에서 실제로 최적해를 준다는 것이다. 거스름돈 문제가 대표적이다. 730원을 거슬러줘야 할 때, 가장 큰 동전부터 쓴다. 500원 하나, 100원 두 개, 10원 세 개. 매 단계에서 '지금 쓸 수 있는 가장 큰 동전'을 선택하면, 동전 수가 최소가 된다. 간단하고, 빠르고, 정확하다.
그래서 우리 뇌는 탐욕 알고리즘을 좋아한다. 에너지가 적게 든다. 복잡한 계산이 필요 없다. "지금 가장 좋은 거 해." 끝. 의사결정의 패스트푸드다.
문제는, 거스름돈이 아닌 대부분의 인생 문제에서 탐욕 알고리즘이 실패한다는 것이다.
왜 실패하는지 한 가지 고전적인 예를 보자. 외판원 문제(Travelling Salesman Problem).
서울, 부산, 대전, 광주, 강릉. 다섯 도시를 전부 방문하고 서울로 돌아와야 한다. 총 이동 거리를 최소로 만들고 싶다. 탐욕 알고리즘을 적용하면? 서울에서 출발해서, 가장 가까운 도시로 간다. 대전. 대전에서 가장 가까운 곳? 광주. 광주에서? 부산. 부산에서? 강릉. 강릉에서 서울로 돌아온다.
매 순간 가장 가까운 곳을 골랐다. 합리적으로 보인다. 하지만 전체 경로를 지도에 그려보면 지그재그로 널뛰기를 하고 있다. 서울대전광주부산까지는 괜찮은데, 부산에서 강릉을 가려면 한반도를 종단해야 한다. 처음에 강릉을 먼저 들렀으면 훨씬 효율적이었다.
매 순간의 최선을 모아놓으면, 전체의 최선이 되지 않는다.
인생에서 이 패턴은 어디에나 있다.
연봉. 대학 졸업 후 첫 직장을 고른다. A 회사는 연봉 4,000만 원, B 회사는 3,200만 원. 탐욕 알고리즘: A. 당연히 A다. 800만 원이나 차이 나잖아. 하지만 A는 성장이 정체된 산업이고, B는 지금은 작지만 2년 후 폭발적으로 성장하는 스타트업이다. 5년 뒤 A에서 연봉 5,000만 원을 받을 때, B에서 시작한 동기는 스톡옵션까지 합쳐 2억을 번다. 지금 이 순간의 800만 원 차이가 5년 뒤의 1억 5천만 원 차이로 뒤집힌다.
인간관계. 주말에 시간이 생겼다. 오래된 친구가 만나자고 한다. 그런데 새로 알게 된 업계 사람이 네트워킹 모임에 초대했다. 탐욕 알고리즘: 네트워킹 모임. 당장의 '유용함'이 더 크니까. 하지만 10년 뒤, 당신의 곁에 남아 있는 건 네트워킹 모임에서 만난 사람이 아니라, 그 주말에 만나지 못한 오래된 친구다. 네트워킹의 즉각적 보상은 컸지만, 우정의 장기적 보상은 비교할 수 없이 크다.
건강. 오늘 저녁, 운동을 갈까 치킨을 시킬까. 탐욕 알고리즘: 치킨. 지금 이 순간의 만족감은 치킨이 압도적이다. 운동의 보상은 오늘 밤에 오지 않는다. 3개월 뒤에 온다. 탐욕 알고리즘은 3개월 뒤를 볼 수 없다. 오직 오늘 밤의 행복만 최적화한다. 그래서 우리는 치킨을 시킨다. 매일 밤.
그렇다면 탐욕 알고리즘의 반대는 뭘까?
컴퓨터 과학에서는 동적 프로그래밍(Dynamic Programming)이라는 방법이 있다. 이름은 거창하지만 핵심은 하나다. 지금의 선택이 미래에 미치는 영향까지 고려해서 결정한다.
외판원 문제에서 동적 프로그래밍은 이렇게 작동한다. "대전이 가장 가깝지만, 대전을 먼저 가면 나중에 강릉-서울 구간이 비효율적이 된다. 차라리 처음에 강릉을 가는 게 전체 경로가 짧아진다." 지금의 한 걸음이 남은 모든 걸음에 어떤 영향을 주는지 계산하는 것이다.
인간의 언어로 번역하면 이렇다. "지금 최선이 뭐냐?"가 아니라 "이걸 선택하면 나중에 뭐가 달라지냐?"를 묻는 것.
연봉 4,000만 원의 A 회사를 고를 때, "5년 뒤 이 산업은 어떻게 될까?"를 한 번만 물어봐도 결정이 달라질 수 있다. 네트워킹 모임을 갈 때, "이 관계는 1년 뒤에도 남아 있을까?"를 한 번만 생각해봐도 오래된 친구에게 전화를 걸게 된다. 치킨을 시킬 때, "3개월 뒤의 나는 오늘의 나에게 뭐라고 할까?"를 한 번만 상상해봐도 운동복에 손이 간다.
하지만 한 가지 고백해야 할 것이 있다. 동적 프로그래밍은 느리다.
탐욕 알고리즘이 패스트푸드라면, 동적 프로그래밍은 코스 요리다. 미래의 모든 경우의 수를 고려하려면 엄청난 계산이 필요하다. 컴퓨터에게도 부담이고, 인간의 뇌에게는 더 부담이다. 모든 결정을 할 때마다 "10년 뒤의 나"를 소환해서 상의할 수는 없다.
그래서 현실적인 해법은 이것이다. 작은 결정에는 탐욕 알고리즘을 쓰고, 큰 결정에는 동적 프로그래밍을 써라.
점심 메뉴, 넷플릭스 영화, 오늘 입을 옷. 이런 건 그냥 지금 끌리는 걸 고르면 된다. 탐욕 알고리즘이면 충분하다. 잘못 골라도 내일 다시 고르면 된다. 되돌릴 수 있는 결정에는 속도가 중요하다.
하지만 직업, 결혼, 주거, 건강. 되돌리기 어렵거나 비용이 큰 결정에는 한 템포 쉬어야 한다. "지금 가장 좋아 보이는 것"이 아니라 "이것을 선택한 3년 뒤의 나"를 상상해야 한다. 느리고 귀찮지만, 이 결정들이 인생의 전체 경로를 바꾼다.
AI 연구자들도 같은 결론에 도달했다. 모든 문제에 동적 프로그래밍을 적용하면 시간이 너무 오래 걸린다. 모든 문제에 탐욕 알고리즘을 적용하면 최적해를 놓친다. 문제의 크기에 맞는 알고리즘을 쓰는 것. 그것이 진짜 지혜다.
다시 퇴근길이다.
네비게이션이 두 경로를 보여준다. 25분짜리 이면도로와 35분짜리 고속도로. 이번에는 잠깐 멈춘다. "지금 가장 빨라 보이는 길이 정말 빠른 길인가?" 퇴근 시간대의 이면도로가 어떤지 떠올린다. 지난번에 50분 걸렸던 기억이 있다. 오늘은 고속도로를 탄다. 35분 만에 집에 도착한다.
작은 승리다. 하지만 이 작은 승리의 원리는, 직업을 고르고, 관계를 선택하고, 인생의 방향을 정하는 큰 결정에도 똑같이 적용된다.
지금 눈앞의 최선에 손을 뻗기 전에, 한 번만 물어보라. "이건 지금의 최선인가, 전체의 최선인가?"
그 한 번의 질문이 네비게이션이 보여주지 않는 경로를 열어줄 수도 있다. 지금은 10분 느려 보이지만, 결국 먼저 도착하는 길. 탐욕이 보지 못하는 길을, 한 템포의 여유가 보여준다.