백준

백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

그리디 알고리즘이란? "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 거스름돈을 돌려주는 문제를 생각해보자. 우리는 대부분 거스름돈을 돌려줄때 큰 단위의 동전부터 거슬러준다. ex ) 500원을 돌려줘야 한다면, 100원을 5개 주는 것보다 500원을 1개 주는 편이 더 편하다. 하지만 만약에 동전의 단위가 100, 250, 300 이라면, (300 * 1) + (100 * 2) 로 3개로 거슬러주는 것보다는 250 * 2 의 방법으로 2개로 거슬러주는 것이 더 최적의 방법이다. 따라서 그리디 알고리즘은 항상 최적의 해를 제공해주는 것은 아니다. 하지만 만약 이 상황에서 큰 단위의 수부터 거슬러줘야하는 조건이 존재할 때 그리디 알..