Greedy.md

그리디 알고리즘

그리디 알고리즘이란?

• 탐욕법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

  • 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함

• 일반적인 상황에서는 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음

  다만, 코테 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 됨

• 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 제시됨

대표 예제: 거스름돈

- **그리디로 풀리는 이유:**
    
    가지고 있는 동전 종류에서 큰 단위가 작은 단위의 배수 형태여서 그럼
    
1. **남은 돈: 1260원**
    
    점원에게 1260원이 있고 이제 손님에게 거스름돈을 거슬러줘야함
    
2. **남은 돈: 260원**
    
    500원 짜리로 거슬러줄 수 있는 돈은 1000원임
    
    500원 * 2개 사용
    
3. **남은 돈: 10원**
    
    50원 * 1개 사용
    
4. **남은 돈: 0원**
    
    10원 * 1개 사용
    

```jsx
n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)
```

탐욕적으로 문제에 접근 했을 때 정확한 답을 찾을 수 있다는 보장이 있을 경우에는 매우 효과적이고 직관적이다!!!