Greedy Algorithm
Imagine you are at a bakery, and you are told you can pick five pastries, one at a time. If your goal is to get the most total sugar, and you choose the sweetest available pastry at every single step without thinking about what is left for later, you are acting greedy.
In computer science, a greedy algorithm is a problem-solving strategy that makes the optimal choice at each immediate stage, hoping these local choices lead to the best global outcome.
💡 The Core Philosophy: Local vs. Global
The absolute core of a greedy algorithm can be summarized in one rule: Make the best possible choice right now.
- Local Optimum: The best decision at the current step.
- Global Optimum: The overall best solution to the entire problem.
A greedy algorithm never reconsiders its past choices. It is a forward-only, short-sighted approach that focuses entirely on immediate reward.
⚙️ How It Works (Step-by-Step)
When a greedy algorithm tackles a problem, it follows a simple, repetitive loop:
- Selection: Choose the best candidate from the current available options.
- Feasibility: Check if this candidate violates any rules or constraints.
- Union: Add the chosen candidate to your growing solution set.
- Check: Determine if the complete problem is solved. If not, repeat.
🛑 The Catch: Why Greed Isn't Always Good
Greedy algorithms are fast and easy to design, but they have a major flaw: they do not always find the absolute best overall solution.
Example: Making Change
Suppose you need to give $36 in change using the fewest number of bills, and your available denominations are $30, $20, $10, and $1.
The Greedy Approach: You take the largest possible bill first ($30). You are left with $6. The largest bill you can take now is $1, repeating this 6 times.
Result: 7 bills ($30 + $1 + $1 + $1 + $1 + $1 + $1).
The Optimal Approach: If you looked ahead, you would see that taking a $20 bill and a $10 bill leaves you with $6, which still requires six $1 bills (8 bills total).
Wait, let's look at another combination: what if we had $15 bills?
Let's use a cleaner standard failure case. You need to make 12 cents using 9-cent, 6-cent, and 1-cent coins:
Greedy: Takes 9¢ first. Needs three 1¢ coins to finish. Total = 4 coins (9, 1, 1, 1).
Optimal: Takes two 6¢ coins. Total = 2 coins (6, 6).
Because the greedy algorithm was blinded by the immediate value of the 9¢ coin, it missed the better global combination.
🏆 When Does Greed Actually Work?
Greedy algorithms work perfectly on problems that exhibit two specific properties:
Greedy Choice Property: A global optimal solution can be reached by making local optimal choices.
Optimal Substructure: The optimal solution to the big problem contains optimal solutions to its smaller sub-problems.
Famous Real-World Examples:
Dijkstra’s Algorithm: Finding the shortest path on a map (like Google Maps).
Huffman Coding: Compressing data files (like creating a ZIP file).
Kruskal’s & Prim’s Algorithms: Finding the cheapest way to connect networks (Minimum Spanning Trees).
📝 Summary
Greedy algorithms are like driving a car by only looking at the five feet of road directly in front of your bumper. It is an incredibly fast, efficient way to travel if the road is straight and predictable. However, if there are hidden turns or complex intersections ahead, being short-sighted might prevent you from ever reaching your true destination.