눈앞의 최선을 고르기

지금 최선을 집어요

거스름돈 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원 둘로밖에
못 메우게 됐기 때문이에요.
지금의 큰 한 걸음이
나중을 망친 거죠.
그래서 동전이 평범할 땐 맞고,
이렇게 어긋난 동전엔 틀려요.
탐욕이 통하는지는
문제마다 확인해야 해요.

정리

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

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

탐욕은 가장 단순한 욕심이에요.
지금 좋은 걸 고르고 앞으로 나아가요.
빠르고 가벼워서 매력적이지만,
그 단순함이 가끔 함정에 빠지죠.
언제 통하고 언제 안 통하는지
그 감을 잡았다면
이제 한 가지를 더 보탤 수 있어요.
전부 따져보는 더 신중한 방법,
그건 다음에서요.