그리디 알고리즘의 이해 파이썬

그리디 알고리즘단계의 첫번재 문제를 풀어보았다

 

문제링크

그냥 단순히 가장큰 단위로 채우고 점점 작은단위로 채우는게 가장 적은수의 동전개수를 사용할것같다는생각이든다

 

반례가 있다

K가 100일때

동전의 종류로 97, 1 50 이 주어졌을때이다

 

어떻게 해아할지 몰라 답을 찾아보았다

해답 링크

단순하게 가장큰단위부터 아래로 천천히 채우는방식이었다

이방식으로는 반례를 해결할수없다 

그렇지만 일단 답이라고 하니 바로 제출해보았다

정답이었다

분명 최소값을 구하라고했다...?

 

그리디 알고리즘에대해 잘설명 해놓은 웹사이트를 찾았다

링크

그리디 즉 욕심쟁이 알고리즘이다

동적프로그램이 지나치게 많은 일을 한다는것에서 착안하여 고안되었다

미래를 생각하지않고 그단계에서 최선의 선택을 하는 방법이다

 

모든상황에서 먹히진않지만 특정조건하에 통하는 문제다

 

다시 문제로 돌아와보니 내가 놓쳤던 부분이 있었다는걸 발견했다 

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)라는 조건이있었다

즉 나보다 더 높은 숫자의 동전은 항상 적은 단위의 동전의 배수만큼의 가치를 지닌다는것

이말은 곧? 가장 큰 가치의 동전을 사용하는게 무조건 이득이라는 말과 같다

 

특정조건하에서 통한다는게 무슨말인지 정확하게 이해했다

 

뭔가 아쉬워서 동적프로그래밍으로도 구현해보았다이코드는 동전의 가치가 굳이꼭 배수관계가 아니여도 사용된 동전의 최소개수를 구해낸다

 

코드제출을 하지못하기때문에 정확하다고 장담은 못하겠지만 본문 예제 2개와 3 100, 1 97 50에서는 정확한 값을 구했다

N, K = map(int, input().split())
dp=[0 for i in range(K+1)]
coins=[]
for i in range(N):
    coins.append(int(input()))
for i in range(1,K+1):
    la=[]
    for j in coins:
        if i-j>=0:
            if dp[i-j]!=-1:
                la.append(dp[i-j]+1)    
    try:
        dp[i]=min(la)
    except:
        continue

print(dp[K])