탐욕(Greedy)그리디알고리즘/동적(Dynamic)계획법 비교

Greedy 계획법과 Dynamic 계획법에 대해 알아보자.

 

 

예시

---

당신은 출발지A에서 도착지B로 가려고 한다.

A에서 B로 가는 방법은 2가지가 있다.

 

• 출발하기전 신호등, 교통상황, 대중교통, 가는거리를 모두 알아보고 가는방법과,
• 일단 출발해서 그때 그때 상황에 따라서 가장 빠른 방법으로 앞으로 나아가는 방법이 있다.

전자의 경우를 동적계획법, 후자의 경우를 탐욕법 

---

 

장단점

Dynamic 알고리즘

동적 계획법의 경우, 점화식을 이용하여 모든 상황을 계산하기 때문에 최적의 경로를 구할 수 있다.

하지만, 그만큼 계산하는데 오랜 시간이 걸린다는 단점이 있다.

Greedy알고리즘

탐욕법의 경우, 각 단계에서 최적의 상황만을 선택하기 때문에, 빠르게 문제 해결이 가능하다.

하지만, 모든 경우를 살펴보지 않기 때문에 최적이 아닌경우가 있거나, 혹은 풀리지 않는 경우가 있다.

 

따라서 이 2가지 계획법은 서로 상호보완적이다.

 

---

예시

시작점에서 출발하여 작은값을 구하는 알고리즘

 

1. 탐욕법 : 시작점에서 7<10이므로 작은값 7 선택 ---> 12<15이므로 12선택

2. 완전탐색 : 시작점에서 모든 경우를 살펴본다.

                 가장 작은값인 5를 선택하기 위해 10선택--->5선택