알고리즘_그리디 알고리즘

1.탐욕 알고리즘(그리디)

최적화 문제를 해결한다.
가능한 해중에서 가장 좋은 해를 찾는 문제
현재 상태에서 욕심내서 선택하는 알고리즘(근시안적)
한번 선택된것은 결코 버려지지 않는다.
근사알리즘의 형태로 탐욕 알고리즘을 많이 사용할 수 있다.

1.2. 예시

• 동전 거스름돈
  현재 거스름돈에서 가장 큰 액면의 동전을 먼저 사용하는것
  최소 동전을 사용해 돈을 거슬러 줘야한다.

ex)
거스름돈 액면: 500,100,50,10,1,0
거스름돈: 752원
1. 거스름돈이 500보다 클때 500원 사용,
2. 거스름돈이 100보다 클때 100원 사용,
3. 거스름돈이 50보다 클때 50원 사용,
4. 거스름돈이 10보다 클때 10원 사용
(500원,1) (100원,2) (50원,1) (1원,2) = 6

1.3. 그리디 동전의 문제점

거스름돈의 단위가 잘못될 경우 최소 동전의 수를 계산할 수 없다.
(이러한 문제는 동적계획 알고리즘을 해결가능하다)

ex)
거스름돈 액면: 500,160,100,50,10,1,0
거스름돈: 200원
1. 거스름돈이 500보다 클때 500원 사용,
2. 거스름돈이 100보다 클때 100원 사용,
3. 거스름돈이 50보다 클때 50원 사용,
4. 거스름돈이 10보다 클때 10원 사용
알고리즘의 해:(160원,1) (10원,4) = 5개
최적 해: (100원,2) = 2개