탐욕 알고리즘(Greedy Algorithm)

*탐욕 알고리즘

탐욕 알고리즘(Greedy Algorithm)

- 결과값에 대하여 생각하지 않고 최선의 옵션을 선택하여 문제를 해결하는 알고리즘

  - 즉, 지역적(locally)의 최선의 선택이 전역적(globally)의 최상의 결과값을 생성하도록 하는 것을 목표로 하는 알고리즘.

- 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘

  - 탐욕 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 됨

    - 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이 아니라 현 시점의 정보 를 바탕으로 가장 이익이 되는 원소들을 선택함. 

- 동적 계획법(Dynamic Programming)과 마찬가지로 최적화 문제(Optimization Problem) 를 푸는데 사용함. (예: MST)

- 탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만, 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장을 하지 못함.

  - 몇몇의 경우에 대해서는 잘못된 결과값을 생성해낼 수 있음.

- 탐욕 알고리즘은 결정한 것을 되돌릴 수 없으며, 하향식(Top-Down) 접근 방식으로 작동함.

- 주어진 문제에 대해 최적해를 구하는데 있어서, 문제가 부문제들로 쪼개지고, 각 부문제들의 최적해로부터 효율적으로 최적해를 구하게 될 때 탐욕 알고리즘을 적용함.

- 탐욕 알고리즘의 장점

  - ① 설명하기 쉬움.

  - ② 모든 경우는 아니지만, 다른 알고리즘 보다 더 잘 수행될 수 있음.

    - 복잡한 과정을 거치지 않고, 상황을 종합적으로 판단하는 알고리즘이 아니기 때문

작동 방식

① 시작하기에 앞서 해 집합(Solution Set)은 비어있음.

② 각 단계마다 요소들이 해 집합에 추가됨.

③ 해 집합이 실현 가능해질 때, 현재의 항목이 유지됨.

④ 해 집합이 실현 가능해지지 않은 경우, 현재의 항목은 선택되지 않고 다시는 고려되지 않게됨.

탐욕 알고리즘의 예

Problem: You have to make a change of an amount using the smallest possible number of coins.  Amount: $28  Available coins:   $5 coin   $2 coin   $1 coin

- 해결 방법

1. Create an empty solution-set = { }.  2. coins = {5, 2, 1}  3. sum = 0  4. While sum ≠ 38, do the following.  5. Select a coin C from coins such that sum + C < 28.  6. If C + sum > 28, return no solution.  7. Else, sum = sum + C.  8. Add C to solution-set.  Up to the first 5 iterations, the solution set contains 5 $5 coins. After that, we get 1 $2 coin and finally, 1 $1 coin.

탐욕 알고리즘 적용

- 선택 정렬(Selection Sort)

- 최소 신장 트리(MST: Minimum Spanning Tree)

- Prim MST 알고리즘(Prim MST Algorithm)

- Kruskal MST 알고리즘(Kruskal MST Algorithm)

- Dijkstra MST 알고리즘(Dijkstra MST Algorithm)

- 허프만 코딩(Huffman Coding)

- Ford-Fulkerson 알고리즘(Ford-Fulkerson Algorithm)

- 배낭 문제(Knapsack Problem)

- 단일 출발지 최단 경로 문제(Single-Source Shortest Path Problem)

- 작업 스케쥴링 문제(Job Scheduling Problem)

---

내용 참고 : https://www.programiz.com/dsa/greedy-algorithm