그리디 알고리즘

그리디 알고리즘이란?

최적해를 구하기 위해 매 순간마다 가장 최적인 선택을 하는 알고리즘이다.

그리디 알고리즘의 문제해결법

선택 절차: 현재 상태에서의 최적의 값을 선택한다.

적절성 검사: 선택된 값이 문제의 조건을 만족하는지 검사한다.

해답 검사: 원래의 문제가 해결되었는지 검사하고, 
해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

그리디 알고리즘 특징

그리디 알고리즘은 간단하고 직관적인 접근 방식을 가지고 있어 구현하기 쉽고 실행 속도가 빠른 편이다.
하지만 최적해를 보장하지 않기 때문에 항상 정답을 찾을 수 있는 것은 아니며, 때로는 최적해에 근접한 해를 구할 수도 있다.

예시

탐욕 알고리즘의 문제 해결 절차 적용

1. 선택절차

• 거스름돈 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을
  우선적으로 선택한다.

2. 적절성 검사

• 선택절차 과정을 통해 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
• 초과한다면 마지막으로 선택한 동전 삭제 후, 1번 과정으로 돌아가 1단계 작은 동전을 선택한다.

3. 해답검사

• 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
• 액수가 부족하면 1번 과정부터 다시 반복

문제풀이

n=int(input())
c=[500,100,50,10] #동전 리스트

ans=0 #동전 개수
for i in c: #큰 동전부터 계산
	ans+=n//i #거스름돈을 초과할 때까지 해당 동전으로 나눠준다
	n%=i #나머지
	
print(ans)

문제 해결 절차를 통해 얻은 해답

• n이 1260일 때 가장 가치가 높은 동전 500원 2개를 먼저 거슬러주고 잔액을 확인한 뒤, 이후 100원 2개, 50원 1개, 10원 1개의 순서대로 거슬러 줌으로써 거슬러줄 동전개수는 총 6개가 된다.