✅ Brute-force
✅ Greedy

✅ Brute-force(완전 탐색)

• Brute-force(완전탐색) 방법은 문제 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
• 모든 경우의 수를 테스트 한 후, 최종 해법을 도출하는 방법이기

✅ Greedy(탐욕)

• Greedy알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법이다.
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각하는 방법을 선택해서 진행하여 최종적인 해답에 도달한다.
• 각 선택의 시점에서 이루어지는 결정은 지역적으로 봤을 때 최적이더라도, 그 선택들을 계속 수집해서 최종적인 해답을 만들었다고 해서 그것이 최적의 해라는 보장은 없다.
• 일반적으로, 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy접근방식이라고 생각하면 된다.

동작 과정

1. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가한다.
2. 실행 가능성 검사 : 새로운 부분해 집합이 문제의 제약 조건을 위반하지는 않는지 ㅇ때문에 해답을 찾아내지 못할 확률은 작다. 하지만 수행 속도가 느리다는 단점이 있다.
3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다.
   아직 전체 문제의 해가 완성되지 않았다면 1번부터 다시 시작한다.

대표적인 예시 - 거스름돈 줄이기

어떻게하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

1. 해 선택 : 당장 가장 좋아보이는 해는 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수가 줄어들기 때문에 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가
2. 실행 가능성 검사 : 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 확인. 초과한다면 마지막에 추가한 후 동전을 거스름돈에서 빼고 1번으로 돌아가 현재보다 한 단계 작은 단위의 동전을 추가
3. 해 검사 : 거스름돈을 확인해서 액수가 모자라면 다시 1번으로 돌아가서 거스름돈에 추가할 동전을 고른다

거스름돈 줄이기 code(python)

n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
    count+= n//coin#해당화폐로거슬러줄수있는동전의개수세기 
    n %= coin
print(count)