탐욕 알고리즘(Greedy - 그리디)

---

1. 탐욕 알고리즘(Greedy - 그리디)

 그리디 알고리즘은 매번 항상 최적의 답안을 선택하여 적절한 해를 구해내는 알고리즘입니다. 탐욕 알고리즘은 과정이 직관적이기 때문에 일반적으로 시간 복잡도가 낮고, 구현이 단순하여 빠르게 동작합니다. 이때문에  이해하기 쉽고 구현하기 간단합니다. 하지만 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우가 많습니다.

---

2. 탐욕 알고리즘의 특성

(1) 탐욕적인 선택조건(Greedy Choice Property)

 

: 각 단계에서 내리는 최적의 선택이 결국 전체 문제에 대한 최적해로 이어질 수 있어야 합니다.

 

(2) 최적 부분 구조(Optimal property)

 

: 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있어야 합니다.

 

---

3. 동전 문제를 통한 탐욕 알고리즘의 동작 과정

 탐욕 알고리즘의 대표적인 문제중 하나인 동전 문제를 통해 탐욕알고리즘의 동작 과정을 설명해 보겠습니다.

 

<문제 설명>

---

주어진 금액을 500원, 100원, 50원, 10원 동전으로 거슬러 줄 때, 최소 동전의 개수를 구하라.

 

 

 「문제 풀이 과정」

 

(1) 가장 큰 단위의 동전부터 사용: 그리디 알고리즘은 항상 현재 상태에서 최선의 선택을 합니다. 이번 동전 문제에서는 최소 동전의 수를 구해야 합니다. 따라서 가장 큰 단위의 동전부터 사용하여 남은 금액을 줄여 나갑니다.

 

(2) 남은 금액 계산: 가장 큰 단위의 동전으로 최대한 거슬러 주고 남은 금액을 계산합니다.

 

(3) 반복: 남은 금액에 대해 다시 가장 큰 단위의 동전부터 사용하여 (1) ~ (2)와 같은 과정을 반복합니다.

 

(4) 종료 조건: 남은 금액이 0이 되거나 더이상 거슬러 줄 수 없다면 종료합니다.

 

---

예제

거슬러 줄 금액이 1260원인 경우.

 

첫번째 단계

가장 큰 금액의 500원 동전을 사용합니다.

1260원을 500원 동전으로 나누면 2개를 사용할 수 있습니다.

남은 금액은 1260 − (500 × 2) = 260원입니다.

 

두번째 단계

다음으로 가장 큰 금액의 100원 동전을 사용합니다.

260원을 100원 동전으로 나누면 2개를 사용할 수 있습니다.

남은 금액은 260 − (100 × 2) = 60원입니다

 

세번째 단계

다음으로 큰 금액의 50원 동전을 사용합니다.

60원을 50원 동전으로 나누면 1개를 사용할 수 있습니다.

남은 금액은 60 - 50 = 10원입니다.

 

네번째 단계

남은 금액이 10원임으로 10원짜리동전 하나를 사용합니다.

---

1260원을 거슬러 주기 위해 필요한 최소 동전의 개수는

-500원 동전: 2개

-100원 동전: 2개

-50원 동전: 1개

-10원 동전: 1개

로  총6개입니다.

---

동전문제를 직접 풀어봅시다.

https://www.acmicpc.net/problem/11047

《소스코드》

#include <stdio.h> 

using namespace std;

int coin[15];

int main()
{
	int i;
	int n, k;
	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d", &coin[i]);
	}
	int ans = 0;
	for (i = n - 1; i >= 0; i--) {
		if (k < coin[i]) continue;
		else {
			ans += k / coin[i];
			k %= coin[i];
		}
	}
	printf("%d", ans);
	return 0;
}