Greedy 알고리즘

그리디 알고리즘이란?

: 기본 조건을 만족시키는 가능한 모든 해결책 중에서 가장 좋은 해결책으로, 근시안적으로 가장 좋아보이는 것을 선택하고, 선택한 뒤에는 절대 뒤로 돌아가지 않는다.

Coin change problem

: 여러 종류의 동전이 있고 동전의 개수가 무제한일 때 동전의 개수가 최소가 되게 거슬러주는 것

→ 가장 큰 액면가를 가진 동전을 선택할 경우 총 동전의 개수가 줄어든다.

해당 문제가 그리디 알고리즘인 이유

• (거스름돈의 남은 금액보다 크지 않은) 가장 큰 동전을 고른다.

  → 주어진 동전의 액면가만을 사용하여 해결책을 찾는다.
  

• 더 나은 선택지가 있더라도 한 번 선택했으면 바꾸지 않는다.

알고리즘

Input: the total change, W output: the total number of coins change ← W, n500 ← 0, n100 ← 0, n50 ← 0, n10 ← 0, n1 ←0 while ( change ≥ 500 ) change ← change-500, n500 ←n500+1 while ( change ≥ 100 ) change ← change-100, n100 ←n100+1 while ( change ≥ 50 ) change ← change-50, n50 ←n50+1 while ( change ≥ 10 ) change ← change-10, n10 ←n10+1 while ( change ≥ 1 ) change ← change-1, n1 ←n1+1 CoinChange = n500+n100+n50+n10+n1

1. 각 종류의 동전을 몇 개씩 거슬러 줘야 하는지 저장하기 위한 변수를 만든다.
2. 거슬러줄 돈이 500원보다 큰 경우에만 change에서 500원씩 빼주면서 500의 개수를 하나씩 늘려준다. 남은 액수가 500원 이하일 경우 while 루프는 끝이난다.
3. 4번의 while 루프가 끝난다면 100원을 사용하며 4번과 마찬가지로 반복해준다.