Tong's Blog

오늘은 Greedy Algorithm(탐욕 알고리즘)에 대해서 알아보겠습니다. 탐욕 알고리즘은 Dynamic Programming과 마찬가지로 가장 최적화를 하기 위해서 만들어진 알고리즘입니다. 이 알고리즘을 탐욕 알고리즘이라고 부르는 이유는 탐욕 알고리즘의 기본 원칙이 더보기 각 단계에서 가장 최적의 답만을 선택한다. 이기 때문입니다. 미래를 생각하는 것이 아니라 지금 현재 단계만을 가지고 답을 도출하기 때문에 마치 욕심쟁이 같다고 생각되어 탐욕 알고리즘이라는 이름을 얻게 되었습니다. 그렇다면 일반적으로 탐욕 알고리즘을 사용하는 경우는 언제일까요? 탐욕 알고리즘은 최적화를 하기 위해 고안된 알고리즘이지만 다이나믹 프로그래밍과 다르게 모든 경우에서 최적의 답을 구해주진 않습니다. 위에서 언급했듯이 현재 ..