Greedy(탐욕)

' 현재 상황에서 지금 당장 좋은 것만 고르는 방법 '

' 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형 '

- 최단 경로를 빠르게 찾아야 하는 문제는 플로이드 워셜(Floyd-Warshall) or 다익스트라(Dijkstra) 알고리즘을 알고 있어야한다. 특히, 다익스트라 알고리즘은 그리드 알고리즘으로 분류됨

- 그리디 알고리즘이면서도 ' 암기 ' 가 필요한 알고리즘

- But 단순 암기를 통해 모든 문제를 대처하기는 어렵다는 점을 이해하자

 

1. 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민

2. 그리디 알고리즘으로 해결 방법을 찾을 수 없다면??? -> 다이나믹 프로그래밍, 그래프 알고리즘 고려

 

# 거스름돈

- 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니라, 무작위로 주어진 경우는 그리디 알고리즘 X

=> 다이나믹 프로그래밍으로 해결 가능

https://cord-ai.tistory.com/163

다이나믹 프로그래밍(Dynamic Programming)

Code

https://github.com/kimmy-git/Algorithm_Test/tree/main/Greedy_Theory

GitHub - kimmy-git/Algorithm_Test