[JAVA] 그리디(Greedy)

그리디(Greedy) 알고리즘

Greedy(탐욕법)
= 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
= 관찰을 통해 탐색 범위를 줄이는 알고리즘

 

이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.
3. 구현해서 문제를 통과한다.

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

최댓값: 5 -> 7 -> 9 로 거쳐가면 21이란 최댓값이 나온다.

그리디 알고리즘 풀이는?
루트 노드 5에서 시작하여 7, 10, 8 중 가장 큰 10을 선택하고, 4, 3 중에 4를 선택한다.