What is Greedy Algorithm? 그리드 알고리즘을 알아보자.

---

Greedy Algorithm

최적해를 구하는 데 사용하는 근시안적인 방법. 매 선택에서 지금 이순간 최적의 답을 계속 선택하여 결과를 도출하는것을 말한다.

1. 여러 경우 중 하나를 결정해야 할 때마다 그 순간이 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하여 해결함.

2. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

3. 일반적으로, 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.

거스름돈 줄이기

500원 100원 50원 10원 동전이 있다. 고객이 3800원 금액을 구매하고, 5천원을 받았을때 최소한의 동전수로 거스름돈을 주려고 한다.
500원 선택 -> 500원 선택 -> 100원 선택 -> 100원 선택 (총 1200원)

500원 400원 100원 50원 10원 동전이 있다. 고객이 3800원 금액을 구매하고, 5천원을 받았을때 최소한의 동전수로 거스름돈을 주려고 한다.
500원 선택 -> 500원 선택 -> 100원 선택 -> 100원 선택 (총 1200원)

400원 짜리 동전을 추가하였지만 그래도 500원이라는 가장 큰 단위로 거스름돈을 선택하는게 최선이다. 결국에는 100원짜리 2개가 추가되어 총 4개의 동전을 줘야한다.(최선의 선택)

전체적으로 봤을때는 400원짜리 동전 3개만 주면 동전 3개로 거스름돈을 줄 수 있다.(최적의 선택)
400원 선택 -> 400원 선택 -> 400원 선택 (총 1200원)

경로 탐색

• 그리디 알고리즘을 통해 1에서 7로 이동하고자 한다.

• 1번노드에서 가장 비용이 적게드는 간선을 통해 이동한다. 비용이 1이 발생하는 2번 노드로 이동한다.

• 비용이 3이 발생하는 4번 노드로 이동한다.

• 비용이 2이 발생하는 3번 노드로 이동한다.
• 비용이 4이 발생하는 5번 노드로 이동한다.
• 비용이 1이 발생하는 7번 노드로 이동한다.
  
  

그리디 알고리즘을 통해 경로를 선택한 결과
1번노드->2번노드->4번노드->3번노드->5번노드->7번노드

• 하지만 전체적으로 봤을때는 1번노드->2번노드->4번노드->7번노드가 최종적으로 최적의 경로이다.

참고 자료

• PB님의 블로그
• SW Expert Academy