그리디(Greedy) 알고리즘 이해(Python 예제 포함)

본 포스팅에서는 그리디(Greedy) 알고리즘에 대해 알아봅니다.

1.  그리디 알고리즘이란?

그림 1.  Greedy 사전 검색 결과 (출처: 네이버 영어사전)

그리디(Greedy)는 그림 1 에서 보실 수 있듯이 사전적 의미로서 "탐욕스러운"이라는 뜻을 갖고 있습니다(그림 2 참고).  즉, 그리디 알고리즘은 주어진 문제를 프로그래밍을 통해 탐욕스럽게 풀어내는 알고리즘입니다. 여기서 "탐욕스러운"이라는 말은 그리디 알고리즘이 주어진 상황에서 최선의 옵션만 선택하며 현재의 선택이 향후에 미칠 영향은 고려하지 않는다는 의미입니다.

그림 2. 탐욕스러운 생쥐 (출처: https://pxhere.com/ko/photo/1076461)

2.  특징

그리디 알고리즘 문제에서는 주로 "가장 큰 숫자 순서대로" 혹은 "가장 짧은 경로 순으로"와 같은 조건을 제시해 줍니다. 이러한 조건은 대체로 정렬 알고리즘으로 해결할 수 있다는 점에서 그리디 알고리즘은 정렬 알고리즘과 세트로 주어지는 경우가 많죠. 그리디 알고리즘을 통해 항상 모든 알고리즘 문제에 있어서 '최적의 해'를 도출할 수 없을 가능성이 높습니다. 따라서 주어진 조건을 충족한다는 전제에서 그리디 알고리즘을 통해 '최적의 해'를 구한 해법이 반드시 정당한지 검토해야 합니다.

3.  연습 문제 (난이도: 하)

그리디 알고리즘의 가장 대표적인 예시 문제는 거스름돈 계산 문제입니다.

Q.  당신은 카페의 계산을 도와주는 직원이며 카운터에는 거스름돈으로 사용하는 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정한다. 손님에게 제공해야 할 돈이 R일 때 거슬러 줄 수 있는 동전의 최소 개수를 구하는 코드를 작성하시오. 단, 거슬러 주는 돈 R은 항상 10의 배수이다.

입력 예시

1460

출력 예시

8

정답 소스코드는 아래 링크를 통해 공개하겠습니다.

heytech.tistory.com/45

알고리즘 스터디#1: 그리디(Greedy) 알고리즘(거스름돈 문제 소스코드)

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 건강한 하루 보내시길 바랍니다 :)

고맙습니다.