Greedy Algorithm
What Is a Greedy Algorithm?
The greedy algorithm is essentially similar to other algorithm pattern approaches that I wrote to solve pattern journals(divide and conquer, Two pointers, sliding windows, frequency counter). It is designed for solving optimization problems; optimization problems are problem demands or require either minimum or maximum result; this includes the Greedy method, Dynamic Programming, and Branch and Bound. However, the approaches between these terms are different, but they are all under optimization problems.
Formal Definition
A greedy algorithm makes greedy choices to ensure it is efficient and optimized. It is an algorithm paradigm that follows the problem-solving approach of making the locally optimal choice at each stage with the hope of finding a global optimum. However, generally, greedy algorithms do not provide globally optimized solutions.
Pros and Cons
Pros: It is easy to come up with a greedy algorithm and analyze the run time rather than something like Divide and conquer.
Cons: The problem with greedy algorithms is that it is hard to prove the algorithm is correct. Understanding why the algorithm is right involves a lot of creativity.
Example Problem:
Let’s dive into one example of a greedy algorithm problem in binarysearch.com. Here is the problem:
Intuition
In this problem, each “?” can have either a 1, 2, or 3, but no two adjacent digits are the same. We want to return the smallest number we can make as a string; therefore, we must choose each character greedily to be as small as possible from left to right.
Implementation
We are lopping over the digits from left to right- if the digit is not a question mark, we must include whatever the number is. Else, we compare the next number in sequence with the one we just appended.
Usually, there are five components in greedy algorithms:
- A candidate (set, list, etc), from which a solution is created.
- A selection function, which chooses the best candidate to be added to the solution.
- A feasibility function, which determines the best candidate to be added to the solution.
- An objective function, which assigns a value to a solution, or a partial solution, and
- A solution function, which will indicate when we have discovered a complete solution.
When to use Greedy Algorithms?
A lot of seemingly tough problems can be solved with Greedy algorithms. Coming up with a correct solution might be easy but proving the correct one might be a struggle. All the greedy problems share a common property that a local optimum can eventually lead to a global minimum without reconsidering the set of choices already considered.
Example of popular greedy algorithm problem :
- Activity selection problem
- Huffman Coding
- Job Sequencing Problem
- Fractional Knapsack Problem
- Prim’s Minimum Spanning tree Algorithm
So there you go, that’s a greedy algorithm. Thank you for reading, and I hope you can learn something!
Reference: