[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm)이란? 탐욕 알고리즘 : 선택의 순간마다 당장 눈에 보이는 최적의 상황만을 쫓아 최종 해답에 도달하는 방법 순간마다 하는 선택은 작게 보아 최적이지만, 그 선택들을 수집하여 도달한 최종 해답이 최적이라는 보장은 없다.

아래의 예시와 같이, 루트 노드부터 시작해서 거치는 노드의 값의 합을 최대로 하는 문제가 있을 때 [case 1] 초록색과 같이 완전 탐색을 통해 노드의 값이 가장 큰 선택을 하는 경우 (5 - 7 - 9) [case 2] 파란색과 같이 탐욕 알고리즘을 통해 매순간 최적의 해만 고르는 경우 (5 - 9 - 3) 탐욕 알고리즘이 항상 최적의 해를 보장하지는 않는다는 것을 확인할 수 있습니다. 탐욕 알고리즘을 사용하는 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황을 제공합니다.

'가장 큰 순서대로' '가장 작은 순서대로' 탐욕 알고리즘(Greedy Algorithm) 문제 해결법 선택 절차 : 현재 상태에서 최적의 해답 선...

요청 처리 중입니다...

[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)

등록된 다른 글