Greedy Algorithm

The Greedy Approach

• 탐욕 알고리즘은 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달한다
• 그 순간의 선택은 그 당시(local)에는 최적이다. 그러나 최적이라고 생각했던 해답들을 모아서 최종적인(global)해답을 만들었다고 해서, 그 해답이 궁극적으로 최적이라는 보장이 없다.
• 따라서 탐욕 알고리즘은 항상 최적의 해답인지 검증이 필요하다.

탐욕 알고리즘 설계 절차

1. 선정 과정

• 현재 상태에서 가장 좋을 것이라고 생각되는(greedy)해답을 찾아서 해답 모음(solution set)에 포함 시킨다

2. 적정성 점검 ex) 밑의 동전 예시에서 거스름돈을 초과하면 선택하지 않는다.

• 새로 얻은 해답 모음이 적절한지결정한다.

3. 해답 점검

• 새로 얻은 해답 모음이 최적의 해 인지를 결정한다.

🤗 최소 동전 개수 문제

def coin_count(value):
	coni_types = [500, 100, 50, 10] (정렬된 리스트)
	coin_count = 0

	for coin in coin_types:
	    count += value // coin # 몫 ->> 거슬러 줄 수 있는 동전 개수 
	    value  =value % coin # 나머지 ->> 거슬러 주고 남은 금액
    
	return coin_count

print(coin_count(1000))

코드를 보면 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 k개라고 할 때 위 소스 코드의 시간 복잡도는 O(K)이다. 즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.