그리디(탐욕법)

정의 및  장단점

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다.

현재 상황에서 지금 당장 좋은 것을 고르는 방법을 의미한다.

그리디 문제는 매우 다양한 문제가 있으며 미리 유형을 외우고 있지 않아도 알고리즘 문제를 풀 가능성이 높다.

그렇지만 많은 문제를 풀어보는 연습이 필요하다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.

 

구현방법

보통 while문이나 조건문을 통해 구현이 된다.

 

문제 예시

그리디 문제의 대표적인 예시로 거스름돈 문제가 있다.

예를 들어 3800원을 거슬러줄 때 최소 지폐,동전수를 구하여라 등의 문제이다.

n =1260
count = 0

coin_types = [500,100,50,10]

for coin in coin_types:
	count += n //coin #해당 화폐로 거슬러 줄수 있는 동전의 개수 세기
    n%=coin
    
print(count)

 

 

 

참고문헌

이것이 코딩테스트다(나동빈 지음)