728x90
거스름돈 문제
-
[알고리즘] 탐욕법 알고리즘(Greedy Algorithm)프로그래밍/알고리즘 2024. 9. 17. 22:01
탐욕법 알고리즘(Greedy Algorithm)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 최적화 문제를 해결하기 위해 사용하는 알고리즘 방법 중 하나이다. 예시) 노드의 합이 가장 높은 방법을 생각해보자. 이 처럼 탐욕법 알고리즘은 매 단계에서 현재 상황에서 가장 최선의 선택을 하는 방식으로 최종 해답을 찾지만 항상 최적의 값을 보장하는것은 아니다. 이러한 탐욕법 알고리즘은 모든 상황에서 보다는 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. - 탐욕 선택 속성(greedy choice property) 이전 단..