탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘(혹은 그리디 알고리즘)은 최적해를 구하는 방법 중 하나다.

매 순간마다 가장 최적인 것을 선택하는 방식으로, 최적해를 찾는다.

• 가장 적은 동전으로 환전하기
  

탐욕 알고리즘은 가장 큰 동전부터 하나씩 환전하며

최적해를 찾는다.

       

이렇게 동전이 2개가 있을때, 1000원을 환전하면

500원 : 2개

100원 : 0개

총 2개의 동전으로 환전 가능하다.

• 탐욕 알고리즘의 문제

              

여기에 600원 동전을 추가해보자

위와 같이 1000원을 환전해보면

600원 : 1개

500원 : 0개

100원 : 4개

총 5개의 동전으로 환전 가능하다.

이렇게 탐욕 알고리즘은 항상 최적의 결과를 보장하지 않는다.

//환전 알고리즘

//Coins(내림차순 정렬이 되어 있어야함) : 환전 가능한 동전 배열,

//NumberOfType : 동전의 갯수, Money : 환전할 금액

void Algorithm::CoinChange(int Coins[], int NumberOfType, int Money)

{      

        int *count = new int[NumberOfType];      //환전할 각 동전의 갯수

        int type = 0;                                         //동전의 종류

 

 

        printf("환전 금액 : %d 원\n", Money);

 

        //환전할 각 동전 0으로 초기화

        for (int i = 0; i < NumberOfType; i++)

               count[i] = 0;

 

        //마지막 동전을 체크할때까지 반복

        while (type < NumberOfType)

        {

               //현재 동전이 금액보다 더 크다면 : 금액이 더 작은 동전으로 변경

               if (Coins[type] > Money)

               {

                       type++;

               }

               //현재 동전이 금액보다 작다면 : 동전 갯수를 하나 올림 & 동전의 금액만큼 돈에서 차감

               else if (Coins[type] < Money)

               {

                       Money -= Coins[type];

                       count[type]++;

               }

               //현재 돈전 = 금액 이라면 : 동전 개수 하나 올림 & 반복 종료

               else

               {

                       Money = 0;

                       count[type]++;

                       break;

               }

        }

 

        //각 동전 갯수 출력

        for(int i = 0; i < NumberOfType; i++)

               if(count[i] != 0)

                       printf("%d동전 %d개\n", Coins[i], count[i]);

 

        //환전하지 못한 금액 출력

        if(Money != 0)

               printf("환산 불가능한 금액은 %d원\n", Money);

 

        //동전 배열 해제

        delete count;

        count = NULL;

}