그리디 알고리즘

그리디 알고리즘이란?

현재 상황에서 지금 당장 좋은 것만 고르는 방법->매순간 가장 좋아보이는 것을 선택, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 ex)가장 큰 순서대로, 가장 작은 순서대로

*다익스트라 알고리즘은 그리디 알고리즘이면서 암기가 필요한 알고리즘

그리디 알고리즘의 정당성

모든 문제에 적용할 수 있는 것은 아님->탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을때 사용!

대표적 그리디 알고리즘 문제

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

n=1000-int(input())
count=0
while(n>0):
    if n>=500:
        n-=500
    elif n>=100:
        n-=100
    elif n>=50:
        n-=50
    elif n>=10:
        n-=10
    elif n>=5:
        n-=5
    else:
        n-=1
    count+=1

print(count)