olrlobt

탐욕법 : 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm)이란 여러 가지 선택지 중에서 지금 이 순간 최적이라고 생각되는 것을 선택하는 알고리즘이다. 지금 당장 최선의 선택을 하므로, 정답을 항상 구할 수는 없다. 하지만, 그리디 알고리즘 자체가 최적의 해를 구하는 것이 아니라, 상대적으로 최적의 해에 가까울 수 있는 해를 구하는 알고리즘이다. 예를 들어, 아래 그림과 같이 Start에서 층을 내려가면서 숫자의 최댓값을 구하는 문제가 있다고 하자. Start에서 시작을 했을 때, 5와 10중에 최댓값에 더 최적화된 선택지는 10이 된다. 그리고 그다음 선택지인, 1과 2중에 최댓값에 더 최적화된 선택지는 2가 되므로, 위 문제를 그리디 알고리즘으로 해결..