[알고리즘] 그리디(Greedy) 알고리즘(탐욕법)

목차

• Greedy 알고리즘 개념
• Greedy 알고리즘 예시
• Greedy 알고리즘 다른 문제들

 

 

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

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 즉, 전후 결정에 관계없이 당시 "가장 최고"라고 생각되는 것을 선택해서 최적의 해를 구하는 방법
• 대표적인 예시로 MST(최소신장트리) 알고리즘, 다익스트라(Dijkstra) 알고리즘, 거스름돈 문제가 있다

 

 

그리디 알고리즘 쉬운 예시

<거스름 돈 문제>

점원이 계산을 마치고 거스름돈을 돌려주는 상황을 생각해봅시다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 충분히 많이 존재한다고 가정합니다. 손님에게 N원을 거슬러 줘야 할 때, 최소 개의 동전으로 거스름 돈을 줄 방법을 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 

출처: https://namu.wiki/w/%EB%8F%99%EC%A0%84

 

<해답>

• 최소 개수의 동전을 사용하기 위해선 동전 중 가장 큰 단위부터 거스름 돈을 구성하면 됩니다. 
• 먼저 500원으로 거슬러 줄 수 있는 만큼 돈을 주고, 이후 100원, 50원, 10원 순서대로 거슬러 줍니다. 
• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 이 방법으로 항상 최적의 해를 구할 수 있습니다. 

 

 

 

그리디 알고리즘 다른 문제들

✔ MST 알고리즘

[Algorithm/알고리즘 공부] - MST(Minimum Spanning Tree, 최소 신장 트리) - Prim(프림), Kruskal(크루스칼) 알고리즘

[알고리즘] MST(Minimum Spanning Tree, 최소 신장 트리) - Prim(프림), Kruskal(크루스칼) 알고리즘

 

✔ 프로그래머스 그리디 문제

programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

 

✔ 백준(BOJ) 그리디 문제

www.acmicpc.net/problemset?sort=ac_desc&algo=33

문제 - 1 페이지