Greedy Algorithm (그리디, 탐욕 알고리즘)

참고 문헌 :

https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

https://mygumi.tistory.com/121

그리디(Greedy) 알고리즘 :: 마이구미

https://covenant.tistory.com/131

그리디 알고리즘(Greedy Algorithm) 및 백준 문제 추천

---

1. Greedy Algorithm (그리디 알고리즘) 개념 정리

- 최적해를 구하는 방법 중 하나로 매 순간 최선의 선택하는 것입니다.

- 그리디 알고리즘은 항상 최적해를 제공해주지 않습니다. 따라서 그리디 알고리즘을 사용하기 위한 조건으로는 탐욕스러운 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)을 만족해야 합니다.

 

탐욕스러운 선택 조건(greedy choice property) : 이전의 선택이 이후의 선택에 영향을 주지 않아야 합니다.

< 탐욕스런 선택 조건 예시 >

왼쪽을 보면 a에서 b와 c 중에서 어떤 것을 선택하냐에 따라서 {d, e} 또는 {f, g}의 선택권이 주어집니다. 따라서 탐욕스러운 선택 조건에 만족하지 않습니다. 반면에 오른쪽을 보면 a에서 b와 c 중에서 어떤 것을 선택하든 {d, e, f, g}의 선택권이 주어지므로 탐욕스러운 선택 조건에 만족합니다.

 

최적 부분 구조 조건(optimal substructure) : 문제에 대한 최적해가 부분 문제에 대해서는 최적해이어야 합니다.

< 최적 부분 구조 조건 예시 >

이 처럼 값이 10인 정점에서 시작하여 인접한 2개의 정점을 선택하여 정점의 합이 최대를 찾는 다고 했을 때 부분 문제인 하나의 정점을 선택했을 때 정점의 합이 최대일 때 선택하는 정점과 실제 답에서 선택하는 정점이 동일함을 확인할 수 있습니다.

---

2. Greedy Algorithm을 활용한 문제들

1. Optimal Storage on tapes

문제) https://www.acmicpc.net/problem/11399

풀이) https://newbie22.tistory.com/181

 

2. Fractional Knapsack

문제) https://www.acmicpc.net/problem/8980

풀이) https://newbie22.tistory.com/183

 

3. Optimal Merge Pattern

 

4. Minimum cost spanning tree

개념 정리) https://newbie22.tistory.com/177?category=968996

 

5. Huffman Coding

6. Shortest Path : Priority First Search