[Algorithm] 탐욕 알고리즘(Greedy)란 무엇인가?

Greedy Algorithm

Greedy는 “탐욕스러운, 욕심 많은”이란 뜻을 가진 용어로, Greedy Algorithm은 탐욕 알고리즘이라 부른다. Greedy 알고리즘은 이름 그대로 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

 

그리디 알고리즘으로 문제를 해결하는 방법

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

 

그리디 알고리즘의 예로 거스름돈 계산 문제가 있다.

거스름 돈 n이 있고, 500원, 100원, 50원, 10원으로만 거슬러 주어야 할 때, 최소 개수의 동전으로 거슬러 주고, 동전의 개수를 구하는 문제이다.

 

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

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

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

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

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

System.out.println(count);