어떻게 눈앞의 최선을 고르기

지금 최선을 집는다

거스름돈 870원을 줘야 한다고 하자. 탐욕의 방법은 간단하다. 지금 낼 수 있는 가장 큰 동전부터 집는 것이다.
500원 하나, 100원 셋, 50원 하나, 10원 둘.
매번 제일 큰 것을 집었을 뿐인데 금방 끝났어요.

큰 동전부터 눌러 집어요. (870원 → 500 · 100 · 100 · 100 · 50 · 10 · 10)

이것이 탐욕 알고리즘이다. 앞으로 어떻게 될지 멀리 따지지 않고, 그저 지금 이 순간 가장 좋은 것을 고를 뿐이다.
계산이 가벼우니 결정도 빨라요.

전체는 보지 않는다

탐욕의 진짜 특징은 전체 지도를 펼쳐 보지 않는다는 데 있다.
갈림길마다 지금 더 좋아 보이는 쪽으로 한 걸음 내디딜 뿐이다. 앞을 멀리 내다보지 않으니 고민이 적고 빠르다.
대신 한 번 고른 것은 다시 돌아보지 않아요.

갈림길마다 더 큰 수를 눌러 한 걸음씩 나아간다. 전체 지도는 보이지 않고, 눈앞의 둘 중에서만 고른다.

전체를 보지 않는다는 것은 장점이자 약점이다. 빠르다는 것은 장점이다.
하지만 멀리 보지 못하니 지금 좋아 보이던 길이 나중에 막다른 길일 수도 있다.
그래도 어떤 문제에서는 이 빠른 방법이 신기하게도 딱 맞아요.

잘 통할 때

회의실 하나에 회의를 되도록 많이 넣고 싶다고 하자. 시간이 겹치면 안 된다.
탐욕의 비결은 가장 일찍 끝나는 회의부터 잡는 것이다. 일찍 비워질수록 뒤에 더 많이 들어가기 때문이다.
이 욕심은 신기하게도 진짜 최선의 답을 줘요.

가장 일찍 끝나는 회의부터 눌러 잡는다. 겹치는 회의는 저절로 빠지고, 탐욕이 가장 많은 4개를 채워요.

왜 이것이 정답일까? 가장 일찍 끝나는 회의를 고르면 방이 가장 빨리 빈다.
남는 시간이 가장 많으니 그 안에 다른 회의가 가장 많이 들어갈 수 있다. 그래서 한 걸음씩 욕심을 내도 결국 전체가 최선이 된다.
이런 문제에서는 탐욕이 곧 답이에요.

틀리는 반례

이번에는 동전이 이상하다. 1원, 3원, 4원짜리만 있고, 6원을 거슬러 줘야 한다.
탐욕대로 큰 것부터 내면 4원 하나에 1원 둘, 동전이 세 개다. 그런데 3원 둘이면 동전 두 개로 끝난다.
눈앞의 최선이 전체의 최선을 놓친 거예요.

두 방법을 눌러 견준다. 탐욕(4·1·1 → 동전 3개)과 더 나은 길(3·3 → 동전 2개). 탐욕이 함정에 빠졌어요.

탐욕이 틀린 까닭은 4원을 덥석 집은 순간 남은 2원을 1원 둘로밖에 메울 수 없게 됐기 때문이다.
지금의 큰 한 걸음이 나중을 망친 것이다. 그래서 동전이 평범할 때는 맞고, 이렇게 어긋난 동전에서는 틀린다.
탐욕이 통하는지는 문제마다 확인해야 해요.

정리

탐욕 알고리즘을 한 줄로 줄이면 '매 순간 지금 제일 좋아 보이는 것을 고른다'이다. 전체를 보지 않으니 빠르고 간단하다.
거스름돈이나 회의실처럼 어떤 문제에서는 이것이 딱 정답이다. 하지만 이상한 동전이나 꼬인 길에서는 눈앞의 최선이 함정이 된다.
그러니 탐욕은 빠르고 자주 맞지만, 정말 맞는지는 문제마다 따져 봐야 해요.

핵심 네 가지를 차례로 눌러 정리해요. 지금 최선 → 전체 안 봄 → 자주 맞음 → 가끔 틀림.

앞에서 본 동적 계획법이 작은 답을 빠짐없이 모으는 신중한 방법이라면, 탐욕은 그 반대편에 있는 가장 단순한 욕심이다. 지금 좋은 것을 고르고 앞으로 나아간다.
빠르고 가벼워서 매력적이지만, 그 단순함 때문에 가끔 함정에 빠진다.
언제 통하고 언제 통하지 않는지 감을 잡았다면, 다음 레슨에서는 또 다른 꾀를 본다. 아예 주사위를 굴려 고르는 방법이에요.