[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

💡 그리디 알고리즘 (Greedy Algorithm)

👉 매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법

• 빠르게 근사치를 계산할 수 있다.
• 결과적으로는 최적해가 아닐 수도 있다.

---

💡 그리디 알고리즘 예시

👉 Activity Selection Problem

• N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기

Activity	A	B	C	D	E
시작	1	4	2	4	6
종료	5	5	3	7	10

• 종료 시간 기준으로 정렬한다.
• 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택한다.

Activity	C	A	B	D	E
시작	2	1	4	4	6
종료	3	5	5	7	10

1. 가장 먼저 종료되는 C
2. A는 시작시간이 이미 지나버렸으므로 패스
3. 그 다음 일찍 종료되는 B
4. D도 이미 시작했으므로 패스
5. 마지막으로 남은 E를 선택하면 총 3가지 활동을 할 수 있게된다.

👉 거스름돈 (동전의 최소 개수)

1. case 1

• 잔돈 : 890원
• 동전의 종류 : 10, 50, 100, 500
  -> 큰 동전부터 계산한다.

잔돈	500	100	50	10
개수	1	3	1	4

2. case 2 (그리디 알고리즘을 적용할 수 없는 경우)

• 잔돈 : 890원

• 동전의 종류 : 10, 50, 100, 400, 500
  -> 큰 동전부터 계산한다.

• 그리디 알고리즘 결과

  잔돈	500	400	100	50	10
  개수	1	0	3	1	4

• 우리가 원하는 정답 (동전의 최소 개수)

  잔돈	500	400	100	50	10
  개수	0	2	0	1	4

👉 그리디 알고리즘 적용 조건

• 그리디 알고리즘은 빠르지만 최적해를 보장하지는 못한다.
• 아래 두 가지 조건에 해당하는 경우 적용할 수 있다.
  • 탐욕적 선택 특성 (Greedy choice property) : 지금 선택이 다음 선택에 영향을 주지 않는다.
  • 최적 부분 구조 (Optimal substructure) : 전체 문제의 최적해는 부분 문제의 최적해로 이루어진다.