Greedy Algorithms
Greedy algorithms is type of problem solving method in programming tests.
why the word greedy?
Greedy algorithms take irreversible decisions based on a global rule.
- Some values are greedy and dominate other values.
- Making a decision based on the values in the current iteration.
- Throw away previous decisions.
There are two types of greedy problems possible.
| Type | Idea |
|---|---|
| Step greedy | choose next best action |
| Structural greedy | identify dominating constraint and build around it |
Examples
- CPU Task scheduling - the dominating constraint is first chosen.
- Increasing triple sequence - Every step just takes whatever best comes.