1. 그리디 알고리즘이란?
그리디 알고리즘이란 말그대로 Greedy(탐욕)이라는 이름과 같이 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다.
2. 예시
* 거스름돈 문제
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
* 풀이
가장 큰 화폐 단위부터 돈을 거슬러 주는 아이디어로 해결한다.
def solution(money):
answer =0
change = [500, 100, 50, 10]
remain = money
for i in change:
answer += remain // i
remain = remain % i
return answer
3. 그리디 알고리즘 사용 시 주의할 점
그리디는 만족하는 적합한 해를 찾는 것이지 최적의 해를 찾는 방법이 아니다.
최적의 해를 찾기 위해서는 Dynamic Programming(동적 계획법)을 이용한다.
또한, 문제를 풀 때 그리디를 사용해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이 보장되어야 한다.
'Algorytm > 기초' 카테고리의 다른 글
[Algorythm-자료구조] 해시 (0) | 2022.12.03 |
---|---|
[Alhgorythm-개념] 정렬 (0) | 2022.12.01 |
[Algorythm-개념] 동적 계획법 (1) | 2021.09.28 |
[Algorythm-개념] 완전탐색 (0) | 2021.09.26 |