알고리즘
-
[알고리즘] 그리디 알고리즘 _ 백준11047 파이썬💫 Computer Science/Computer Science 2020. 4. 27. 13:39
● Greedy Algorithm 그리디(Greedy) 알고리즘은 'greedy'(탐욕, 욕심쟁이)라는 뜻에서 유추할 수 있듯이 멀리 생각하지 않고 지금 당장의 단계에서 가장 좋은(최선의) 선택을 하는 문제해결 방법입니다. 각 단계에서 가장 좋은 선택을 했을 때 전체적으로 최선의 해결방법이 되길 바라는 알고리즘입니다. 그리디 알고리즘은 동적프로그래밍(다이나믹, DP)에서 지나치게 많은 연산과정을 거치는 것을 보완하기 위해 나온 개념이지만, 모든 문제에서 그리디 알고리즘이 최선의 선택을 보장하는 것은 아니라는 단점이 있습니다. 사실 대다수의 경우 올바른 답을 주진 않지만 쉽고 적은 연산으로 문제를 해결하는데 좋은 결과를 보장한다는 점에서 많이 사용되는 개념입니다. 예시1 - 백준 11047 동전0 그리디 ..