[알고리즘] Greedy 알고리즘

Greedy Method

• 탐욕적인 알고리즘
• 최적화 문제 해결에 용이 : 최대, 최소를 구하는 문제 ( “가장 ~~한 것”을 고르는 문제)
• 결정의 순간 가장 좋다고 생각하는 것을 선택 ⇒ 번복 X !
• 결정의 순간에는 가장 좋았다고 해도 최종 해답에서는 좋지 않을 수 있다.
• 최적의 해를 주는지 반드시 검증해줘야 한다!
• 과정
  • 선정 과정 (selection procedure) : 최단 거리 / 최소 시간 등의 기준을 잡고 그에 맞추어 선택
  • 적정성 점검 (feasiblity check) : 새로 구한 해답이 적절한지 점검. 적절하다면, solution set에 포함시킨다
  • 해답 점검 (solution check) : 해답 모음이 최적의 해인지 결정한다

solution = null

for i=1 to n do              // 최대 n회 반복
	x = SELECT(A)              // 최적의 해를 x에 저장
	if FEASIBLE(solution, x)   // 적정성 점검
		then solution += x       // 적절하면 solution에 포함
	endif
endfor
return(solution)

Greedy 알고리즘의 예제

1. 거스름돈 문제
   • 동전의 수가 최소가 되도록 한다
   • 거스름돈 x 를 넘어가지 않는 동전 중, 가장 가치가 큰 동전을 준다
   • ex) 1600원 거스름돈 → 1000원 + 500원 + 100원 → 3개
   • ex) 잘못된 해답 : 100원 * 16 → 16개
2. Fractional Knapsack 문제
   • n개의 물건과 1개의 배낭이 있고, 배낭에는 무게 M 까지 넣을 수 있다.
   • 이 때 물건의 이윤이 최대가 되도록 x만큼 넣는다
   • 물건의 무게 : w / 물건의 값어치 : P

   

   
   
   • Greedy 방식 : 같은 무게 당 이윤이 가장 큰 물건을 넣는다
   • 잘못된 방식 : 가벼운 무게 순, 이윤이 큰 순
3. 0-1 Knapsack 문제
   • 위의 문제와 같으나, 물건을 쪼개어 담을 수 없다
   • 잘못된 방식 : 가벼운 순, 이윤이 큰 순, 무게 당 이윤이 큰 순
   • 버리는 부분이 최소이며 이윤이 크도록 담아야 한다