그리디 알고리즘

[그리디 알고리즘] 그리디 알고리즘의 설명과 간단한 코테 예제풀이

그리디알고리즘(Greedy Algorithm) 그리디(Greedy)란 '탐욕스러운, 욕심 많은' 이란 뜻이다. 그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방식이다. 하지만 순간의 최적의 선택을 한다고 해서 최종적인 해답이 최적이라는 보장이 없다. 따라서 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들일때 그리디 알고리즘을 적용할 수 있다. 여기서 가장 중요한 점은 그리디 알고리즘을 이용하면 최적해를 찾지 못할 수 도 있다는 것을 항상 명심해야한다. 그렇다면 그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 어떤 조건을 만족할까? 1. greedy choice property : 현재 선택이 이 후의..