그리디(Greedy)

그리디(Greedy) 알고리즘

탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.

아래처럼 5 -> 7 -> 9 로 거쳐가면 21이란 최댓값이

루트 노드 5에서 시작하여 7, 10, 8 중 가장 큰 10을 선택하고, 4, 3 중에 4를 선택