Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Greedy Algorithm #6

Closed
jimin-kiim opened this issue Apr 28, 2023 · 0 comments
Closed

Greedy Algorithm #6

jimin-kiim opened this issue Apr 28, 2023 · 0 comments

Comments

@jimin-kiim
Copy link
Owner

jimin-kiim commented Apr 28, 2023 •
edited
Loading

Introduction

  • grabs data items in sequence. each time with best choice(local optimal choice. not a global optimal). without thinking future.
  • local optimal: "in terms of my view point". from intuition, heuristic experiences
  • when it seems to be solved with DP but the cost is expensive
    • optimal substructure -> DP
    • optimal substructure + greedy choice property -> Greedy

Design

  • Step 1. selection ( local optimal choice, ranking)
  • ( Step 2. verifying feasibility, if the result of selection meets the constraints )
  • Step 3. solution check and termination. whether to stop or to continue to find better solution

Analysis

T(n) = differ by algorithms and data structure

Algorithm Examples of Greedy Algorithm

  • Prim's algorithm
  • Kruskal's algorithm
  • Dijkstra algorithm
jimin-kiim added a commit that referenced this issue May 1, 2023
@jimin-kiim
Merge pull request #9 from jimin-kiim/#6
80d9c09 
#6 Greedy Algorithm
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@jimin-kiim