그리디 알고리즘

그리디 알고리즘이란?

매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법이다.
그리디 알고리즘은 근사치를 빠르게 계산할 수 있지만 결과적으로는 최적해가 아닐 수도 있다.

그리디 알고리즘 적용 조건

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

그리디 알고리즘 예시1

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

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

• 종료 시간을 기준으로 오름차순 정렬
• 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택 => C, B, E

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

그리디 알고리즘 예시2

• 거스름돈 (동전의 개수 가장 적게)
  • 잔돈 : 890
  • 동전 종류 : 10, 50, 100, 500 (동전들끼리 서로 구성관계이므로 greedy 사용가능)
  • 큰 동전부터 계산한다.

동전	500	100	50	10
개수	1	3	1	4

• 거스름돈 (동전의 개수 가장 적게)
  • 잔돈 : 890
  • 동전 종류 : 10, 50, 100, 400, 500 (동전들끼리 서로 구성관계이므로 greedy 사용가능)
  • 큰 동전부터 계산한다.

<그리디 알고리즘 결과>

동전	500	400	100	50	10
개수	1	0	3	1	4

<내가 원하는 답>

동전	500	400	100	50	10
개수	0	2	0	1	4