그리디 - 2. 기본적인 그리디 알고리즘 구현

📌 2. 기본적인 그리디 알고리즘 구현

✅ 학습 목표

이 단원에서는 그리디 알고리즘을 C언어로 구현하는 방법을 배우고, 간단한 문제를 해결하면서 그리디 알고리즘의 개념을 이해하는 것이 목표입니다.

1. 그리디 알고리즘을 C언어로 직접 구현하는 방법 학습
2. 간단한 문제를 해결하면서 그리디 개념 익히기
3. 거스름돈 문제를 통해 그리디 알고리즘의 적용 방식 이해

---

✅ 학습 내용

1. 동전 거스름돈 문제

그리디 알고리즘의 대표적인 예제 중 하나인 거스름돈 문제를 다룹니다.
이 문제에서는 최소한의 동전 개수로 거스름돈을 줄 수 있도록 해결합니다.

🔹 문제 설명

• 손님에게 거스름돈 1260원을 줘야 합니다.
• 사용할 수 있는 동전은 500원, 100원, 50원, 10원 입니다.
• 거스름돈을 줄 때 최소한의 동전 개수를 구하는 프로그램을 작성하세요.

---

✅ C언어 코드 예제

#include <stdio.h>

int main() {
    int money = 1260;  // 거스름돈
    int coin_types[4] = {500, 100, 50, 10};  // 사용 가능한 동전 종류
    int count = 0;  // 동전 개수 카운트

    // 가장 큰 동전부터 차례로 나누기
    for (int i = 0; i < 4; i++) {
        count += money / coin_types[i];  // 해당 동전 개수 추가
        money %= coin_types[i];  // 남은 금액 갱신
    }

    printf("최소 동전 개수: %d\n", count);
    return 0;
}

📌 출력 결과

최소 동전 개수: 6

---

✅ 핵심 원리

이 문제는 그리디 알고리즘을 적용하기에 적절한 문제입니다.
이유는 항상 가장 큰 단위의 동전부터 사용하면 최적의 해를 보장하기 때문입니다.

그리디 알고리즘 적용 방식

1. 가장 큰 단위의 동전부터 차례로 나눕니다.
   • 1260 ÷ 500 = 2 → 500원 2개 사용, 남은 돈: 260원
   • 260 ÷ 100 = 2 → 100원 2개 사용, 남은 돈: 60원
   • 60 ÷ 50 = 1 → 50원 1개 사용, 남은 돈: 10원
   • 10 ÷ 10 = 1 → 10원 1개 사용, 남은 돈: 0원
2. 최소한의 동전 개수를 사용하여 해결할 수 있음.
3. 그리디 알고리즘이 적용될 수 있는 조건을 만족함.
   • 탐욕적 선택 속성(Greedy Choice Property): 가장 큰 동전부터 선택해도 전체 최적해를 보장함.
   • 최적 부분 구조(Optimal Substructure): 부분 문제를 반복하여 해결 가능.

---

✅ 주의할 점

그리디 알고리즘은 모든 경우에서 항상 최적의 해를 보장하는 것은 아닙니다.
이 문제에서는 500원, 100원, 50원, 10원과 같이 특정한 동전 단위가 주어졌기 때문에
그리디 알고리즘을 사용해도 최적해를 보장할 수 있습니다.

그러나 동전 단위가 다르게 주어지는 경우
(예: 500원, 400원, 100원, 50원, 10원)에는 그리디 알고리즘이 최적해를 보장하지 못할 수도 있습니다.
따라서 그리디 알고리즘이 적용 가능한 문제인지 항상 확인하는 과정이 필요합니다.

---

✅ 정리

1. 거스름돈 문제는 그리디 알고리즘을 적용하기 좋은 대표적인 문제이다.
2. 가장 큰 단위의 동전부터 차례로 사용하는 방식으로 해결할 수 있다.
3. C언어 코드를 통해 이를 직접 구현해 보면서, 그리디 알고리즘이 어떻게 동작하는지 익힐 수 있다.
4. 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니므로, 적용 가능성을 판단하는 것이 중요하다.