[알고리즘] 탐욕(Greedy) 알고리즘

탐욕(Greedy)

• 사전적으로 '탐욕스러운, 욕심 많은' 이라는 뜻으로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒는것
• 지금 이 순간 당장 최적인 답을 찾는다.
• 항상 최적의 결과를 도출하지는 않지만, 최적에 근사한 값을 빠르게 도출 할 수 있다.

 

탐욕 알고리즘 단계

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사 : 원래의 문제가 해결 되었는지 검사, 해결이 안되었다면 선택 절차로 돌아가 반복

 

탐욕 알고리즘 적용 예시

• 주로 거스름돈 문제가 나오는듯 하다.
• 편의점 알바중 물건의 값이 4230원이 나왔고 손님은 5000원을 냈다. 거스름돈을 줄때 동전의 갯수를 최소한으로 거슬러 줘야한다. 동전은 500,100,50,10원이 있다.
• 단순하게 생각하면 거스름돈은 770원이므로, 500원 1개, 100원 2개, 50원 1개, 10원 2개 이다. 

1. 선택 절차 : 가장 가치가 큰 동전을 먼저 고려한다. 500원
2. 적절성 검사 : 선택절차에서 선택한 동전을 더할때 총합이 안넘는지 확인하고 넘으면 선택절차로 돌아가 한 단계 낮은 동전을 선택한다.
3. 해답 검사 : 선택된 동전들의 합이 거스름돈과 일치하는지 검사. 아니라면 1번 부터 다시 반복

// 거스름돈 배열 coin{500,100,50,10}, 거스름돈 change
int greedy (int[] coin, change){
  
  int i=0;  // 인덱스
  int total=0; // 동전의 합
  int count=0; // 동전 갯수 카운팅
  
  while(true){ // 반복문
   if(total+coin[i] > change){  // 동전의 합이 거스름돈을 넘는다면
      i++; // 다음동전 인덱스
      continue; // 다시 반복문 처음으로
   }
   total += coin[i]; // 해당 동전의 값 합계에 더하기
   count++; // 동전 카운팅
   if (total == change) break; // 동전의 합이 거스름돈과 같아진다면 반복문 나오기
  }
  return count++;  // 동전 카운트 반환 
}

 

탐욕 알고리즘을 적용하기 위한 문제 조건

• 문제가 마시멜로 실험과 같다면 탐욕 알고리즘을 사용 할 수 없다.
• 마시멜로 실험이란 마시멜로를 1개를 주고 먹지않고 15분을 참으면 1개를 더 주기로하는 것인데 
  탐욕 알고리즘 매순간 최선의 선택만 하므로 15분을 기다리지 않고 1개를 먹게된다.
• 탐욕 알고리즘을 적용하기 위한 문제의 조건은
  1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부문 문제에 대한 최적 문제 해결 방법으로 구성된다.