인생은 선택의 연속입니다. 우리는 매 순간 "지금 당장 좋은 것"을 선택할지, 아니면 "미래를 위해 지금은 참을지" 고민합니다. 알고리즘 세계에도 이런 고민이 있습니다. 탐욕 알고리즘(Greedy Algorithm)은 그 이름처럼 "미래는 모르겠고, 지금 당장 눈앞에 보이는 최선의 이익만 쫓겠다"는 전략입니다. "탐욕적이라니 나쁜 거 아닌가?"라고 생각할 수 있지만, 이 단순무식한 방법이 복잡한 계산을 획기적으로 줄여주는 열쇠가 되기도 합니다. 오늘은 마시멜로 실험에 빗대어 그리디 알고리즘의 본질을 파헤쳐 보겠습니다.
1. 탐욕 알고리즘(Greedy)이란?
탐욕 알고리즘은 문제를 해결하는 과정에서 매 단계마다 지금 이 순간 가장 좋아 보이는 것을 선택하는 방식입니다. 나중에 어떤 영향이 있을지는 고려하지 않습니다. 이를 '지역적 최적해(Local Optimum)'를 찾아서 '전역적 최적해(Global Optimum)'에 도달하려는 전략이라고 부릅니다.
1-1. 마시멜로 실험과 그리디
아이 앞에 마시멜로 하나를 두고 "15분을 기다리면 하나 더 줄게"라고 말합니다. - 그리디 전략: "기다리는 건 싫어! 지금 당장 먹을래." (눈앞의 마시멜로 1개 획득) - 비(非) 그리디 전략: "참으면 2개가 되니까 기다려야지." (미래를 고려해 2개 획득) 이 비유에서 볼 수 있듯이, 그리디 알고리즘은 항상 최적의 결과(마시멜로 2개)를 보장하지는 않습니다. 하지만 결정이 매우 빠릅니다.
2. 그리디가 통하는 완벽한 예시: 동전 거스름돈 문제
그리디가 가장 빛을 발하는 순간은 '거스름돈'을 줄 때입니다. 손님에게 1,260원을 거슬러 줘야 하는데, 동전 개수를 최소한으로 해서 주고 싶습니다. (동전: 500원, 100원, 50원, 10원)
전략: 무조건 가장 큰 단위의 동전부터 낼 수 있는 만큼 냅니다. 1. 500원짜리로 줄 수 있는 만큼 준다. -> 2개 (1,000원) / 남은 돈 260원 2. 이제 100원짜리로 줄 수 있는 만큼 준다. -> 2개 (200원) / 남은 돈 60원 3. 50원짜리로 준다. -> 1개 (50원) / 남은 돈 10원 4. 10원짜리로 준다. -> 1개 (10원) / 끝 결과적으로 동전 6개로 깔끔하게 해결됩니다. 큰 단위의 동전이 작은 단위 동전의 배수이기 때문에, 작은 것을 모아서 큰 것을 만드는 것보다 큰 것을 먼저 쓰는 게 무조건 이득이기 때문입니다.
3. 그리디가 실패하는 경우: 배수의 법칙이 깨질 때
하지만 세상이 항상 호락호락하지 않습니다. 만약 동전 단위가 [500원, 400원, 100원]이고, 800원을 거슬러 줘야 한다면 어떨까요?
- 그리디 방식: 일단 가장 큰 500원 1개를 줍니다. 남은 300원은 100원짜리 3개로 줍니다. 총 4개 (500+100+100+100)
- 최적의 해답: 그냥 400원짜리 2개를 주면 됩니다. 총 2개 (400+400)
이처럼 눈앞의 최선(500원 선택)이 전체의 최선(동전 최소 개수)을 망치는 경우가 발생합니다. 이럴 때는 그리디를 쓸 수 없고, 동적 계획법(Dynamic Programming) 같은 더 정교한 알고리즘을 써야 합니다.
4. 그리디 알고리즘 사용 조건
코딩 테스트에서 "이거 그리디로 풀어도 되나?"를 판단하려면 두 가지 조건을 확인해야 합니다.
- 탐욕적 선택 속성 (Greedy Choice Property): 지금의 선택이 이후의 선택에 영향을 주지 않으면서 최적이어야 합니다.
- 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해를 모으면 전체 문제의 최적해가 되어야 합니다.
이 조건이 만족된다면, 그리디 알고리즘은 그 어떤 방법보다 빠르고 강력한 해결책이 됩니다. 내비게이션의 최단 경로 찾기(다익스트라 알고리즘)도 사실은 그리디의 일종입니다.
1. 탐욕 알고리즘은 매 순간 눈앞의 최선을 선택하여 답을 찾아가는 직관적인 방식입니다.
2. 동전 거스름돈 문제처럼 하위 문제의 최적해가 전체 최적해로 이어질 때 가장 효율적입니다.
3. 항상 최적의 결과(Global Optimum)를 보장하지는 않으므로, 적용 가능한 조건인지 검증이 필요합니다.