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

 

 

탐욕법 알고리즘(Greedy Algorithm)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 최적화 문제를 해결하기 위해 사용하는 알고리즘 방법 중 하나이다.

 

 

예시) 노드의 합이 가장 높은 방법을 생각해보자.

 

노드 예시

 

합이 가장 높은 방법

 

탐욕법 알고리즘에 의한 방법

 

 

이 처럼 탐욕법 알고리즘은 매 단계에서 현재 상황에서 가장 최선의 선택을 하는 방식으로 최종 해답을 찾지만 항상 최적의 값을 보장하는것은 아니다.

 

 

이러한 탐욕법 알고리즘은 모든 상황에서 보다는 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다.

 

- 탐욕 선택 속성(greedy choice property)

이전 단계의 선택이 이후 선택에 영향을 주지 않는, 즉 한번 내린 결정이 문제를 풀어나가는 과정에 있어서 되돌릴 수 없는 경우를 의미한다.

 

- 최적 부분 구조(optimal substructure)

문제의 최적해가 부분 문제의 최적해로부터 구성될 수 있는 성질을 의미하며, 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미한다.

 

즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

 

 

---

 

 

근사 알고리즘 (Approximation Algorithm)

근사 알고리즘은 최적의 해를 구할 수 없는 문제에서 최대한 근사한 해를 구하는 알고리즘을 의미한다. 탐욕법 알고리즘은 최적의 해를 보장하지 못하기 때문에 최적해의 '근사 값'을 목표로 하고 있으며, 이는 근사 알고리즘으로 사용할 수 있다. 특히, 정확한 계산 보다는 빠른 속도를 요구하는 알고리즘으로 사용이 가능하다.

 

 

---

 

 

탐욕법 알고리즘 예시)

[ 거스름돈 문제 ]

 

문제.

동전들을 사용하여 특정 금액을 맞추는 문제로, 이 문제의 목표는 가장 적은 개수의 동전으로 거스름돈을 주는 것이다.

 

예를 들어, 다음과 같은 동전 종류가 있다고 가정한다.

• 동전 종류: 1원, 5원, 10원, 50원
• 목표 금액: 93원

 

풀이.

목표 금액 93원을 주기 위해, 큰 동전부터 차례대로 선택한다.

1. 50원 동전 선택: 93원 - 50원 = 43원 (50원 동전 1개)
2. 10원 동전 선택: 43원 - 10원 = 33원 (10원 동전 1개)
3. 10원 동전 선택: 33원 - 10원 = 23원 (10원 동전 2개)
4. 10원 동전 선택: 23원 - 10원 = 13원 (10원 동전 3개)
5. 10원 동전 선택: 13원 - 10원 = 3원 (10원 동전 4개)
6. 1원 동전 선택: 3원 - 1원 = 2원 (1원 동전 1개)
7. 1원 동전 선택: 2원 - 1원 = 1원 (1원 동전 2개)
8. 1원 동전 선택: 1원 - 1원 = 0원 (1원 동전 3개)

최종적으로 사용된 동전의 종류는:

• 50원 동전 1개
• 10원 동전 4개
• 1원 동전 3개

총 8개의 동전이 사용되었다.

 

 

한계점.

만약 동전 종류가 다음과 같이 있다고 가정한다면,

• 동전 종류: 1원, 3원, 4원
• 목표 금액: 6원

4원 + 1원 + 1원으로 3개의 동전이 필요하지만, 여기서 최적해는 3원 + 3원으로 2개의 동전만 필요하게 된다.