[ 알고리즘 ] 6. Greedy 알고리즘

 

 

다이나믹 프로그래밍은 Blind 된 게 많다.

 

어느 것이 Optimal solution인지 판단하기 위해서 계산해야 하는 게 많다.

그렇게 Optimal인지도 모르는 solution을 계산하느라 시간이 많이 날라간다.

 

---

지난 번에 DP를 이용해서 MCM을 구할 땐, 색칠되어 있는 모든 칸들을 계산했다. 

그런 뒤에 값이 가장 최적인 값을 구했다.

 

 

따라서, 어떤 선택이 최선인지 정하고 필요없는 옵션들을 조금 더 제한한다면

더 좋은 성능을 낼 수 있을 것이다. 

 

 

Greedy 알고리즘은 어느 것이 최고의 선택인지 정할 수 있게 해준다.

(당연히 이걸 쓸 수 있는 문제들이 있음, MCM은 DP가 맞음)

 

 

---

Greedy 알고리즘

 

: 매 순간에서 가장 최고의 선택을 한다고 생각하면 된다.

 

ex) 여기에서 가장 괜찮은 식당은 어디일까?

→ (다 먹고) 지금 여기 기준으로 최고의 디저트 가게는 어디일까?

→ (다 먹고) 지금 여기 기준으로 최고의 놀거리는 뭘까?

 

 

※ 주의점 : 항상 Globally optimal soulutin 으로 데려가진 않을 수 있다.

                 * 하지만, 대부분의 상황에서는 Global optimal solution으로 데려간다. 

 

 

예시 1) 잔돈 교환 - 최소 개수의 동전 개수를 받고 싶어함.

- 1000원 받아야 하면 ( 10원짜리 100개를 받고싶어 하지 않음)   

 

알고리즘 :

● 현재 받아야 하는 돈 - ( 거슬러 줄 수 있는 가장 큰 단위 ) 를 연산하고, 그 다음 값들도 똑같이 적용한다.

 

● 매 순간 최고의 선택을 한다.

  760원 있을 때, 거스름 돈에서 최고의 선택 : 500 *1개

  260원 있을 때 , 최고의 선택 : 100 *2개

  60원 있을 때 , 최고의 선택 : 50 *1개

  10원 있을 때 , 최고의 선택 : 10 *1개

 

 

 

 

(출처)

한동대학교 용환기 교수님 - 알고리즘