탐욕 알고리즘(Greedy)

탐욕 알고리즘

    각각의 단계에서 최적의 수를 찾는다

    각 단계에서 국소 최적해를 찾음으로써 최종적으로 전역 최적해를 구하게 된다

    그리디 알고리즘은 100% 최적해를 보장해주지 않는다

 

예시)

동전 문제

가지고 있는 동전이 500, 100, 50, 10, 5, 1 이 있고,

거스름돈이 789원일 때 가장 적은 동전을 주는 방법은?

 

1. 가장 가치가 있는 동전을 먼저 계산하고 다음 가치 있는 동전을 선택하고 계속 반복한다

500원이 가장 크므로 500을 1개 선택한다

 

2. 500원 1개, 100원 2개, 50원 1개, 10원 3개, 5원 1개, 1원 4개가 정답이 된다.

 

 

단점으로 그리디 알고리즘은 100% 최적해를 보장해주지 않는다

 

예시)

물건1 - 크기 40, 가격 10000

물건2 - 크기 30, 가격 6000

물건3 - 크기 20, 가격 5000

크기가 50인 배낭에 넣을 물건의 가격이 합이 최대한으로 한다면?

 

그리디로 계산하면

먼저 가장 가격이 높은 물건을 선택하므로 물건1을 선택하게 된다.

총 가격이 10000원이 되고, 크기가 40이므로 더이상 넣을 수 없다.

 

하지만 물건2와 물건3을 선택하면 

총 가격이 11000원이 된다.

 

따라서 그리디 알고리즘은 항상 최적해를 보장해 주지 않는다.