[알고리즘] 그리디 알고리즘

그리디 알고리즘 선택 과정

 

💡그리디 알고리즘이란?

• 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
• 그리디 해법은 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 검토합니다.

 

 

그리디 알고리즘 예시 문제 

- 문제 : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다.

손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

 

- 입력 : N = 1260 

 

- 풀이 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 식으로 풀이합니다. 먼저 1260원을 500원으로 나누고 그다음은 100원, 50원 순서로 나누면서 개수를 카운트합니다.

 

- 예제 코드

N = 1260
count =0

#큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

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

print(count)

 

- 화폐의 종류가 K라고 할 때 시간 복잡도 : O(K)