[알고리즘] Greedy algorithm

❓ 탐욕적인 알고리즘 (Greedy algorithm)

---

탐욕적인 알고리즘은 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함 으로써 최종적인 해답에 도달한다.

❗️ 하지만, 그 순간의 선택이 그 당시( local )에는 최적이다. 최선이라고 생각했던 답들을 모아서 최종적인 ( gobal) 해답을 만들었다고 해서, 그 해답이 궁긍적으로 최적이라는 보장은 없다!

→ 최적의 해답인지 검증 필요 !!

💫 탐욕적인 알고리즘 설계 절차

---

1. Selection procedure ( 선정과정 )
   • 현재 상태에서 가장 좋으리라고 생각되는 해답을 선택한다.
2. Feasibility check ( 적절성 점검 )
   • 새로 얻은 해답을 해답모음(solution set)에 포함시키는 것이 적절한지 점검한다.
3. Solution check ( 해답 점검 )
   • 새로 얻은 해답모임이 해인지 점검한다.

🔎 Example -Change Problem

---

그리디 알고리즘에 대해 알아보기 위한 예시 알고리즘이다.

problem

동전의 개수가 최소가 되도록 거스름 돈을 주는 문제

Greedy Algorithm

의사 코드

While (there are more coins and the instance is not solved)
	Grab the largest remaining coin; // selection procedure

If (adding the coin makes the change exceed the amount owed) // feasibility check
		reject the coin;

else
		add the coin to the change;
If (the total value of the change equals // solution check
				the amount owed)
		the instance is solved;
}

• while 반복문
  • 동전이 남아 있고 instance가 해결되지 않을 때 반복을 유지
• If (adding the coin makes the change exceed the amount owed)
  • 소유하고 있는 동전 중에 가장 큰 동전을 선택하였지만 목표 치 보다 초과 시 동전 반환
• if (the total value of the change equals the amount owed)
  • 만약 목표 값과 선택한 동전이 일치하면 해결 완료