[CLRS] [15] Greedy Algorithm

1. Greedy Algorithm?

- 매 순간 국소적인 최적해를 찾는 과정을 반복함으로써 전체 문제에 대한 해를 찾는 문제 해결의 한 패러다임

- Greedy Algorithm으로 얻은 해가 전체 문제에 대해 반드시 최적의 해라는것을 항상 보장 불가

 

2. Greedy Algorithm의 최적해를 가질 때

2.1. ex 1) 거스름 돈(각각의 동전들이 배수관계)

https://www.acmicpc.net/problem/11047

n, k = map(int,input().split())

cost = list(int(input()) for _ in range(n))
cnt = 0 

for _ in range(n):
    p = cost.pop()
    cnt += k//p
    k = k%p

print(cnt)

 

3. 결론

- Greedy Algorithms은 특정한 규칙이 있는게 아니고, 현시점에서 가장 중요한것부터 해결해 나가는 알고리즘이다.

- 가장 중요한것을 어떻게 잡냐에 따라 결과는 달라진다. 이를 많은 연습을 통해 직관을 키우는게 중요하다.