[알고리즘 이론] 그리디 알고리즘 - 동전 거스름돈 문제

그리디 알고리즘 - 동전 거스름돈 문제

---

그리디 알고리즘의 동전 거스름돈 문제에 대해서 공부한 내용 정리 입니다 !

 

1. 그리디 알고리즘

2. 동전 거스름돈 문제

---

1. 그리디 알고리즘

가능한 해들 중에서 가장 좋은 해를 찾는 문제에 사용한다.

부분적인 최적 해를 찾고, 이들을 모아서 문제의 최적 해를 구한다.

한 번의 결정이 이후의 결정에 영향을 주지 않는 경우에 최적이다.

 

2. 동전 거스름돈 문제

거스름돈 760원이 있을 때, 우리는 500원 동전 1개, 100원 동전 2개, 50원 동전 1개, 10원 동전 1개까지 총 5개의 동전이 필요하다.

동전 거스름돈 문제는 이처럼 거스름돈 액수에 대한 최소 동전의 수를 구하는 문제이다.

 

public static void main(String[] args) {
    int n500 = 0;
    int n100 = 0;
    int n50 = 0;
    int n10 = 0; 
    int n1 = 0;
    int change = 200;

    while (change >= 500) {
        change = change - 500;
        n500++;
    }

    while (change >= 100) {
        change = change - 100;
        n100++;
    }

    while (change >= 50) {
        change = change - 50;
        n50++;
    }

    while (change >= 10) {
        change = change - 10;
        n10++;
    }

    while (change >= 1) {
        change = change - 1;
        n1++;
    }

    int count = 0;
    count = n500 + n100 + n50 + n10 + n1;

    System.out.println("거스름돈으로 사용된 동전의 개수: " + count);
}

 

코드는 위와 같이 작성할 수 있다.

가장 큰 수를 해결하고 다음으로 넘어가면서 문제를 해결하고 있다.

하지만 동전 거스름돈 문제는 결과가 고정되어 있기 때문에

항상 최적의 답을 주지는 못한다.

 

그렇다면 어떻게 해결하면 좋을까?

한 번의 선택에 대해 다양한 경우를 고려하면 된다.

---

다음 포스팅은 또 다른 그리디 알고리즘에 대하여

공부해보겠습니다요 !