그리디(Greedy) 알고리즘이란?

현재 상황에서 지금 당장 좋은 것만 골라 탐욕적으로 문제를 해결하는 알고리즘 입니다.
매 상황에서 가장 큰 값 또는 가장 좋은 방법으로 보이는 것을 선택하여 그 선택이 나중에 어떤 영향을 줄지는 고려하지 않습니다. 그래서 항상 최적의 해를 보장 해줄수는 없습니다.

• 코딩 테스트에서는 탐욕적으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론해서 해결 가능한 문제들이 출제 됩니다.
• 일반적인 그리디 알고리즘은 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 합니다. 즉 현재 상황에서 가장 좋은 선택만을 선택하여 문제를 해결할 수 있는 능력을 길러야 합니다.
• 그리디는 정당성 분석이 중요 합니다. 이 말이 무슨 말이냐면 가장 좋아보이는 선택을 해도 반복적으로 선택해도 가장 최적의 해를 얻을 수 있는지 확인 해야 한다는 말 입니다.
• 현재 상황에서 가장 좋은 선택을 요구하기 때문에 보통 데이터를 작은 순서나 큰 순서로 정렬해야 할 때가 많습니다. 그래서 정렬 라이브러리 사용 방법을 잘 숙지 하고 있다면 빠르게 문제를 해결할 가능성이 높아진다.

그리디 알고리즘 예시 문제

모두가 그리디 알고리즘을 생각하면 가장 머리에서 떠오르는 문제는 거스름돈을 줄 때 동전의 개수를 가장 적게 줄 수 있는 방법을 구하라는 문제일 것이다.
이 문제의 문제해결 아이디어는 최적의 해를 빠르게 구하기위해 가장 큰 화폐부터 돈을 거슬러주는 것이다.
이 문제 해결 아이디어가 최적의 해를 보장하기 위해서는 가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수로 작은 단위의 동전들을 조합해 다른 해가 나올수 없기 때문 입니다.

input = 1270 # 거슬러줘야 하는 금액 
count = 0 # 거슬러줄때 동전의 개수 
array = [500, 100, 50, 10] # 동전의 종류 
for i in array:
      count += n//i # 가장 큰 화폐부터 거슬러 주기 
      n %= i # 거슬러주고 남은 돈 n에 저장 
print(count) # 총 개수를 출력 

위의 예시 코드처럼 가장 큰 화폐단위의 동전부터 거슬러주면 거슬러주는 동전의 개수를 가장 적게 만들 수 있습니다.