My goal is solve the LeetCode medium.
Now I can solve only easy but I have four months more.
The greedy algorithm is literally a method of reaching a final answer by pursuing only the optimal situation that is visible right in front of you at every moment of choice.
A greedy algorithm is an approximate method used to find an optimal solution.
-> How to solve a greedy algorithm problem
-
Selection Procedure: Choose the best solution for the current state.
-
Feasibility Check: Check whether the selected solution satisfies the condition of the problem.
-
Solution Check: Checks if the original problem has been solved, if not, returns to the selection process and repeats the above process.
In most problems, a greedy algorithm works well if two conditions are satisfied: a greedy choice property and an optimal substructure condition.
The greedy selection condition is that prior choices do not influence subsequent choices, and the optimal substructure condition is that the optimal solution to the problem is also optimal for the subproblem.
Greedy Choice Property: Prior choices do not affect subsequent choices.
Optimal Substructure: The final solution to a problem consists of an optimal solution to the subproblem.
If these conditions do not hold, the greedy algorithm cannot find an optimal solution.
However, even in this case, the greedy algorithm can be used as an approximation algorithm, and in most cases, it can be used practically because of its fast calculation speed.
In this case, too, a rigorous proof is needed to ensure to what extent a solution close to the optimal solution can be obtained.
For a problem with a particular structure, a greedy algorithm can always find an optimal solution.
This structure is called a matroid.
Matroids do not appear in all problems, but because they are found in many places, they increase the utilization of greedy algorithms.
