[algorithm] greedy [python]

Greedy Algorithm은 최적의 해를 구하기 위해

현재 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식.

+ 이러한 선택이 가장 좋을 것이라고 기대하고 사용하는 것 , 현재의 선태이 나중에 미칠 영향에 대해서는 고려하지 않음

 

문제 해결 과정에서 순간마다 최적의 결정

but 항상 최적해가 나오는것은 아님

 

문제에 따라 가장 큰 순서대로, 가장 작은 순서대로 같은 기준을 제시해준다.

 

ex.거스름돈 문제 - 모든 화폐가 서로 배/약수 관계를 가지기때문에 성립함

배약수 관계가 없다면 dynamic programming / graph algorithm 등으로 문제를 해결할 수 있다.

동전이 500원, 100원, 50원, 10원일 경우 - greedy

동전이 500원, 400원, 100원일 경우 - dp ..

 

ex. 백준 2839 [python]

n = int(input())
def function(n:int):
    rem = n % 5
    val = n // 5
    if rem == 0 :
        return val
    elif rem == 1:
        if val < 1:
            return -1
        else:
            return(val-1+2)
    elif rem == 2:
        if val < 2:
            return -1
        else:
            return(val-2+4)
    elif rem == 3:
        return(val+1)
    else:
        if val<1:
            return -1
        else:
            return(val-1+3)
        
print(function(n))