탐욕 기법

탐욕 기법 소개

● 매 번 선택할 때 마다 그 순간에 가장 좋은 선택을 함으로써 최종적인 해에  도달한다.

● 최적인 해들을 모아서 최종 해를 만들었다고 해서, 그 해가 궁극적으로 최적이라는 보장이 없다.

● 따라서 탐욕 기법은 항상 최적의 해를 만들어 내는 지를 반드시 검증해야 한다.

 

선택 기준

● 선택이 실현 가능해야 한다.

● 모든 선택들 중에서 최적이라고 여겨지는  선택을 해야 한다.

● 한 번 선택하면 나중에 되돌릴 수 없다.

 

설계 전략

● 비어 있는 해 모음으로 시작한다.

● 탐욕적인 기준에 따라 해 모음에 추가할 다음 해를 선택한다.

● 새 해 모음이 실현 가능한지를 확인한다. 실현 가능하다면 새 해 모음을 확정하고 아니면 선택한 해를 버린다.

● 새 해 모음이 최종 해라면 종료한다. 아니면 2번으로 간다.

 

거스름돈 문제

● 액면가가 다른 m(≥1)개의 동전들이 있다.

● 동전 i, 1≤i≤m,의 액면가는 d_i이고 d_1>d_2>⋯>d_m=1이다.

● 액면가가 같은 동전들의 개수는 무한히 많이 있다.

● 거스름돈 n(≥1)을 최소 개수의 동전들을 사용하여 주어야 한다.

 

탐욕 알고리즘의 아이디어

주어야 할 거스름돈이 남아 있는 동안 다음을 반복한다.

1. 남은 동전들 중 액면가가 가장 큰 동전을 선택한다.

2. 선택한 동전을 거스름돈에 추가하면 거스름돈이 주어야 할 금액을 초과한다면 그 동전을 버린다. 아니면 그 동전을 거스름돈에 추가하고 주어야 할 거스름돈을 추가한 동전의 액면가만큼 감소시킨다.

주: 최적의 알고리즘

 

최적이 아닌 예

탐욕적인 알고리즘

시간 복잡도

- 입력의 크기: m(액면가가 다른 동전들의 수)

- 기본 연산: 4번의 배정문

- 기본 연산의 수행 횟수: 최대 m

- 시간 복잡도: m = θ(m)