마시멜로를 못 참는 탐욕 알고리즘
크리스가 편의점에서 아르바이트를 하고 있다.
손님이 1260원짜리 물건을 사고 2000원을 냈다. 거스름돈은 740원.
점장님이 신신당부했다. "동전 개수를 최소한으로 해서 거슬러 줘. 동전 아까우니까."
크리스는 고민하지 않고 손을 움직였다.
크리스는 본능적으로 알고리즘을 사용했다.
"지금 당장 선택할 수 있는 것 중 가장 좋은 것(가장 큰 동전)을 고른다."
이것이 바로 **탐욕 알고리즘(Greedy Algorithm)**이다.
1. "지금 이 순간"에 충실해라
동적 프로그래밍(DP)이 "모든 가능성을 기록하며 신중하게 미래를 설계하는 모범생"이라면,
탐욕 알고리즘은 **"미래는 모르겠고, 일단 지금 눈앞에 보이는 이득을 챙기는 욜로(YOLO)족"**이다.
2. 성공 사례: 거스름돈 문제
크리스가 푼 거스름돈 문제는 탐욕 알고리즘이 완벽하게 통하는 대표적인 사례다.
우리나라 동전(500, 100, 50, 10)은 큰 단위가 항상 작은 단위의 배수이기 때문이다.
JavaScript
function minCoins(change) { const coins = [500, 100, 50, 10]; // 큰 동전부터 정렬 let count = 0; for (let coin of coins) { // 1. 당장 이 동전으로 최대한 많이 거슬러 준다. count += Math.floor(change / coin); // 2. 남은 돈을 계산한다. change %= coin; } return count; } console.log(minCoins(740)); // 7 (500x1 + 100x2 + 10x4)
복잡한 재귀나 점화식 없이 반복문 하나로 끝난다. 속도가 엄청나게 빠르다.
3. 실패 사례: 탐욕의 함정
하지만 세상일이 항상 맘대로 되지는 않는다.
만약 동전 단위가 **[500원, 400원, 100원]**이라고 가정해 보자.
손님이 800원을 거슬러 받아야 한다면?
탐욕 알고리즘은 당장의 500원에 눈이 멀어, 400원 두 개라는 더 좋은 수를 놓쳤다.
이럴 때는 탐욕 알고리즘을 쓸 수 없고, 우리가 지난 시간에 배운 **동적 프로그래밍(DP)**을 써야 한다.
4. 언제 써야 할까? (탐욕적 선택 조건)
탐욕 알고리즘은 빠르고 강력하지만, 치명적인 단점(항상 최적해를 보장하지 않음) 때문에 사용 조건이 까다롭다.
실무에서 쓰이는 곳
5. 5장을 마치며
우리는 이제 알고리즘의 주요 패러다임을 모두 섭렵했다.
하지만 알고리즘의 세계에는 정답이 없는 문제들도 있다. 슈퍼컴퓨터로도 몇 억 년이 걸리는 문제들, 그리고 그걸 해결하기 위해 인간이 고안해 낸 기발한 꼼수들.
마지막 6장에서는 전설적인 난제, N-Queen 문제와 NP 문제 이야기를 통해 알고리즘적 사고의 끝을 경험해 보자.
6장 그 밖의 문제들 - 1. N-Queen 문제 편에서 계속된다.