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

✔️ 그리디 알고리즘(탐욕법) 정의

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

최적의 값을 구해야 하는 상황에서, 각 단계에서 최적이라고 생각 되는 것을 선택해 나가는 알고리즘 입니다. 
그리디 알고리즘은 각 단계마다 지역 최적의 해를 찾는 문제로, 문제를 더 작게 쪼개는 형태이다. 

 

➕ 언제 쓰는가?

    최적해를 구하는 문제 !!   

 

✔️ 그리디 알고리즘으로 문제 해결하기

• 선택 절차(Selection Procedure) : 현재 상태에서의 최적 해답을 선택한다.
• 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
• 해답 검사(Solution Check) : 문제가 해결되었는지 확인하고, 해결되지 않았다면 선택 절차로 되돌아간다.

 

✔️ 대표적인 문제

백준 5585번 - 거스름돈 

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

 

만약, 주어진 가격이 380엔이라면 다음과 같은 순서로 문제를 풀 수 있다.

1. 최소 개수의 동전을 거슬러 받기 위해 가장 큰 화폐 단위부터 돈을 거슬러 준다.
2. 500엔으로 거슬러 줄 수 있는 돈은 500엔으로 1개이고 남은 돈은 120엔이다.
3. 남은 돈에서 100엔으로 거슬러 줄 수 있는 돈은 100엔으로 2개이고 남은 돈은 20엔이다.
4. 마지막으로 10엔으로 거슬러 줄 수 있는 돈은 10엔으로 1개이고 남은 돈은 0원이다.
5. 따라서 동전의 최소 개수는 1+2+1인 4가 된다.

// 거슬러 주어야 할 돈
int n = 620;
// 동전의 개수를 셀 count
int count = 0;

// 거스름 돈의 종류를 담은 배열
int[] type = {500, 100, 50, 10, 5, 1};

for (int i = 0; i < type.length; i++) {
	// 500엔 부터 거슬러 줄 수 있는 동전의 개수 세기
	count += n / type[i];
	n %= type[i];
}

출처: https://ittrue.tistory.com/196 [IT is True:티스토리]

 

✔️문제 풀이 리스트

 

[알고리즘 문제 풀이] 백준 11047: 동전 0 (자바) : 그리디 알고리즘

 

[알고리즘 문제 풀이] 백준 1931 회의실 배정 (자바) : 그리디 알고리즘 [중]

 

 

[알고리즘 문제 풀이] 백준 11399 ATM(자바) : 그리디 알고리즘 [하]

 

[알고리즘 문제 풀이] 백준 1080 행렬 (자바) : 그리디 알고리즘

 

 

# 참고 문헌

https://hongcana.tistory.com/41

https://jellili.tistory.com/23

https://ittrue.tistory.com/196