Always pick the best option right now
Day 146 of 149
👉 Full deep-dive with code examples
The Coin Change Analogy
You owe someone $0.63 and want to use the fewest coins:
Greedy approach:
- With common US coins (25¢, 10¢, 5¢, 1¢): 25¢ → 25¢ → 10¢ → 1¢ → 1¢ → 1¢ = 6 coins
- Pick the largest coin that fits, then repeat
That's greedy!
At each step, pick what looks best RIGHT NOW without thinking ahead.
The Problem It Solves
Optimization problems have many choices:
- "What's the shortest route?"
- "How to fit most items in a bag?"
- "Minimum number of steps?"
Checking all combinations can be too slow. Greedy gives a fast answer by repeatedly picking a locally optimal choice.
How It Works
- Make a choice → Pick the best available option
- Reduce the problem → New smaller problem remains
- Repeat → Until problem is solved
No looking back, no reconsidering. Just greedy choices.
When Greedy Works
Classic cases where greedy is optimal (with proof):
- Coin change (for some coin systems, like common US coins)
- Activity scheduling (most non-overlapping events)
- Huffman coding (compression)
Doesn't work for every problem:
- Some problems need to look ahead
- Greedy might miss the globally optimal solution
Greedy vs Dynamic Programming
| Greedy | Dynamic Programming |
|---|---|
| Fast, simple | Slower, more complex |
| Local choices | Considers all options |
| May not be optimal | Can be optimal |
| Use when it provably works | Use when greedy fails |
Note: Dynamic programming can produce an optimal answer when the problem has the right structure (like optimal substructure) and you model it correctly.
In One Sentence
Greedy Algorithms solve problems by picking the best available option at each step, which is fast but only works when local choices lead to a global solution.
🔗 Enjoying these? Follow for daily ELI5 explanations!
Making complex tech concepts simple, one day at a time.
Top comments (0)