Skip to content
BENIBIX Learn

Greedy Algorithm

Development🧮 Algorithms & Data StructuresAlgorithm Design Techniques

Also known as Greedy Method, Greedy Approach

Taking the choice that looks best at each step. It never goes back.

Think of it like

Think of it like grabbing the biggest coin each time you pay. It is quick, but not always best.

Example

Emma makes 6 cents from coins of 1, 3 and 4. Greedy takes 4, 1, 1, three coins, but 3 and 3 needs only two.

Why it matters

When it works it is the fastest way, and Dijkstra's algorithm is one. You must check that it works first.

Definition

A greedy algorithm builds an answer one step at a time. At each step it takes the choice that looks best right now. It never goes back to change an earlier choice. That makes it fast and simple. For some problems it gives the best answer, and for others it misses. Giving change with coins of 1, 5, 10 and 25 works greedily; coins of 1, 3 and 4 do not.

Common mistake

Trusting a greedy answer without proof. The coin case shows how a good-looking choice can lose.

Key takeaways

  1. 1
    Best right now. At each step.
  2. 2
    No going back. Choices are final.
  3. 3
    Fast but risky. Not always the best.

Compare