그리디 알고리즘 정리

현재 상황에서 가장 좋은 선택지를 택하는 알고리즘, 탐욕 알고리즘이라고도 불립니다.

주의할 점으로는 그리디 알고리즘이 최적의 해가 아닌 경우가 있을 수 있어 잘 추론해야 합니다.

 

그리디 알고리즘를 설명하기 가장 좋은 거스름돈 문제

money = 입력값
count = 0  ##거스름돈 갯수 세기

array =[500, 100, 50, 10] ##거스름돈 리스트화

for coin in array:
	count += money // coin  ## 나눈 몫
    	money %= coin  ## money에 coin 나눈 나머지

 

 큰 금액의 동전인 500원부터 차례대로 계산하면 되기에 그리디 알고리즘을 사용하면 풀리게 됩니다.

동전의 금액이 300원 200원 등 이라면 얘기가 다를 수 있기에 문제를 잘 살펴야합니다.

## 여러 수 공백기준 입력 받기 map(int, input().split()) 

## (n // k) * k 를 하면 n이 k로 나누기가 깔끔하게 되지 않아도 가장 근접한 k의 배수의 수를 찾습니다. 

## data = input() #문자열로 입력받는듯? 후 result = int(data[0]) 하면 붙어있는 숫자도 한 숫자씩 저장가능합니다.