알고리즘 그리디(greedy) 알고리즘

●그리디(greedy) 알고리즘 - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

출처 - 위키백과

 

●쉽게 설명하면 모든 경우의 수를 구하는게 아니라 하나를 선택하고, 그 선택한 순간에 최적이라고 생각하는 것을 하나 선택하면서 최적해를 구하는 알고리즘이다. 그렇기 때문에 전체적으로 최적이 아닌 경우가 나올수도 있다. 그래서 그리디 알고리즘을 구현할 때는 전체적인 최적이 될것인지를 염두해 두고 알고리즘을 구현해야 한다.

 

●Dijkstra(다익스트라)의 최단경로 알고리즘이나 최소비용신장트리 같은 알고리즘이 그리디 알고리즘을 이용한 알고리즘이다.

 

●문제 - 가게에서 손님이 1000원을 내고 10원~1000원짜리 물건을 샀을때 동전의 개수를 최소로 해서 거스름돈을 거슬러 주는 알고리즘을 구현하라.(동전은 500원,100원,50원,10원)

#include<stdio.h> int dong[4] = {500,100,50,10};       //동전 단위 int count[4];                              //동전 개수를 저장하는 변수 int flag = 0; int sum; int change; int i = 0; void input(){  printf("거스름돈 입력:\n");  scanf("%d", &change); } void process() {  while(i<4){   sum = dong[i];   if(sum>change){    sum = sum - dong[i];    i++;   }   else if(sum<change)   {    count[i] = count[i]+1;    change = change - dong[i];   }   else if(sum = change){    count[i] = count[i] + 1;    flag = 1;    break;   }  } } void output(){  if(flag == 1){   printf("사용동전\n");   for(i=0;i<4; i++){    if(count[i]>0)    printf("%d 동전은 %d개 사용\n", dong[i], count[i]);   }  }  else{   printf("불가능한 경우이다");  } } void main() {    input();    process();    output(); }