Greedy Algorithm & Divide and Conquer

Magic Framework

Greedy Algorithm

  • Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece.
  • It always chooses the next piece that offers the most obvious and immediate benefit.
  • Greedy fits perfectly for those solutions in which choosing a locally optimal solution also leads to global optimal solution(aka ‘Greedy Choice’).

Divide & Conquer

  • Divide & Conquer is an algorithm design paradigm which works by recursively breaking down a problem into sub-problems of similar type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

출처 : “Data Structures & Algorithms” by DS GUY