DSA Jun 7, 2018 ~ 1 min read

Greedy Algorithm

Photo by Sharon McCutcheon on Unsplash

Overview

A greedy algorithm is an approach that solves problems by making the locally optimal choice at each stage with the hope of finding a global optimum.

Key Characteristics

  • Makes the most reasonable choice in the current situation
  • Mainly applied to combinatorial optimization problems alongside backtracking and dynamic programming
  • Solves problems by making decisions that appear best from the current perspective

Algorithm Steps

  1. Selection Procedure: Select one candidate from the available options that appears to be the best solution in the current situation
  2. Feasibility Check: Verify whether the selected choice is valid and meets the problem’s constraints
  3. Solution Check: Confirm that the accumulated selections satisfy the problem’s requirements

You might also like

Backtracking
DSA Apr 30, 2018

Backtracking

Understanding backtracking and tree search algorithms including DFS, BFS, and Best First Search with practical applications
Big-O Notation
DSA Apr 30, 2018

Big-O Notation

Understanding Big-O notation and time complexity analysis - from O(1) to O(N!) with practical examples
String Algorithms
DSA May 20, 2018

String Algorithms

Understanding string algorithms - palindromes, Manacher's algorithm, tries, and suffix trees with implementations