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

탐욕 알고리즘 Greedy Algorithm

 

탐욕 알고리즘이란?

• 최적화 문제를 해결하는 알고리즘으로 근시안적인 방법이다.
• 그 순간이 최적이라고 생각되는 것을 선택해 나가는 방식이다.
• 각 결정은 지역(local)적으로는 최적이나, 전체(global)적으로 봤을 때 최적이라는 보장은 없다.

 

 

대표 문제

• 동전 문제
• 배낭 문제
• 활동 선택 문제(회의실 배정)
• ...

 

 

동전 문제

Q. 어떻게 거스름돈의 개수를 최소한으로 줄일 수 있을까?

 

[접근방법]

그 당시 거슬러줄 수 있는 가장 큰 액수의 동전을 선택한다.

1. coin = 0 이면 종료
2. coin > 0 이면, coin보다 작거나 같은 동전 중 가장 큰 동전(m)을 선택
3. coin = coin - m
4. 1~3 반복

 

*그러나 이 방법은 모든 coin system에서 동작한다는 것을 보장해주지 못한다.

반례 ex) 100원, 400원, 500원 동전이 있을 때 800원을 거슬러준다면 최소 개수는?

 

	500	400	100	계
Greedy	1	0	3	4
최적해	0	2	0	2

위 표와 같이 Greedy로 풀었을 때는 동전의 개수는 4개 이지만 최적해는 2개임을 볼 수 있다.

따라서 그리디 알고리즘이 모든 coin system에서 동작하지 못한다는 것을 알 수 있다.

 

 

활동 선택 문제

Q. 회의실은 하나고 여러 시간대의 예약이 들어왔다. 이때 최대한 많은 회의가 열릴 수 있게 선택하자

 

[접근방법]

종료시간이 가장 빠른 활동을 먼저 선택하자

• 종료시간이 빠른 순서로 정렬한다.
• 종료시간이 가장 빠른 활동을 선택한다.
• 선택한 활동의 종료시간보다 빠른 시작시간을 가지는 활동들은 모두 제거한다.
• 2~3을 반복한다.