Picking the best right in front of you
You saw it with big-O: how work piles up as the input grows. So what if, instead of weighing everything, you just grab "the best-looking thing right now" at every step? It's fast, genuinely fast. But is it always right?
Grab the best one now
You owe 870 won in change.
How do you do it?
The greedy way is simple.
Grab "the biggest coin
you can use right now" first.
One 500,
three 100s,
one 50,
two 10s.
You just grabbed the biggest each time,
and it was done in a flash.
Click the biggest coin first. (870 → 500 · 100 · 100 · 100 · 50 · 10 · 10)
This is a greedy algorithm.
It doesn't weigh
how things will turn out later.
It just picks "the best one
at this very moment."
The math is light,
so the decision is fast.
It doesn't look at the whole
Here's greedy's real trait.
It never unrolls the whole map.
At each fork
it just takes one step
toward "whichever looks better now."
Since it doesn't peer far ahead,
there's little fuss and it's fast.
But once it picks,
it doesn't look back.
At each fork click the bigger number, one step at a time. The whole map stays hidden; you pick only between the two in front of you.
Not looking at the whole
is both a strength and a weakness.
Fast is the strength.
But since it can't see far,
the path that looked good now
might be a dead end later.
Still, for some problems
this fast method
turns out to fit perfectly.
When it works out
You want to fit as many meetings
as possible into one room.
No overlaps allowed.
The greedy trick is
to grab "the meeting that ends earliest" first.
The sooner the room frees up,
the more can come after.
This bit of greed, amazingly,
gives you the truly best answer.
Click the earliest-ending meeting first. Overlaps drop out automatically, and greedy fills in the most, four of them.
Why is this the right answer?
Pick the one that ends earliest
and the room frees up soonest.
The most open time is left,
so the most other meetings
can fit inside it.
So even being greedy step by step,
the whole turns out best.
For problems like this, greedy is the answer.
The case where it's wrong
This time the coins are odd.
There are only 1, 3, and 4.
You must give back 6.
Go greedy, biggest first:
one 4, then two 1s.
Three coins.
But what about two 3s?
That's done in two coins.
The best in front of you
missed the best overall.
Click to compare the two ways. Greedy (4·1·1 = 3 coins) versus the better path (3·3 = 2 coins). Greedy fell into the trap.
Greedy went wrong because
the moment it grabbed the 4,
the leftover 2 could only be
filled with two 1s.
The big step now
wrecked what came later.
So with ordinary coins it's right,
but with mismatched coins like these it's wrong.
Whether greedy works
has to be checked per problem.
In summary
A greedy algorithm on one line goes like this.
At every step, pick the best-looking thing now.
Not looking at the whole, it's fast and simple.
For some problems, like change or the meeting room,
this is exactly the right answer.
But with odd coins
or a tangled path,
the best in front of you becomes a trap.
So greedy is fast and often right,
but whether it's truly right must be checked per problem.
Click the four key points in order to wrap up. Best now → no whole view → often right → sometimes wrong.
Greedy is the simplest kind of greed.
Pick what's good now and move forward.
It's appealing for being fast and light,
but that simplicity sometimes trips into a trap.
If you've caught the feel
for when it works and when it doesn't,
you can now add one more thing:
a more careful method that weighs everything.
That's for next time.