[Algorithms] Greedy Algorithm | 그리디 알고리즘

[Algorithms] Greedy Algorithm | 그리디 알고리즘

Greedy Algorithm

그리디 알고리즘

- 지금 당장의 최선의 선택지만을 골라가며 해를 도출해나가는 방법을 채택한 알고리즘을 의미한다.

(당장, 눈앞의 이익만을 좇는다.)

- 그리디 알고리즘은 대체로 좋은 결과를 기대할 수 없지만,

특정 문제에서는 그리디 알고리즘이 최적해를 보장해주기도 한다.

(예를 들어, 매트로이드와 같은 특수 구조에서는 그리디 알고리즘이 최적해를 보장한다.)

- 그리디 알고리즘은 최적화 문제를 대상으로 적용할 수 있는데,

최적해를 찾을 수 있다면, 최적해를 찾는데 목표를 두고,

최적해를 주어진 시간에 찾아낼 수 없다면, 그런대로 괜찮은 해를 찾는데 목표를 둔다.

Examples of Algorithm using Greedy Algorithm

[Minimum Spanning Tree; 최소 신장 트리]

* Prim's Algorithm (프림 알고리즘) (URL)

* Kruskal's Algorithm (크루스칼 알고리즘) (URL)

[Single-Source Shortest Path; 단일 시작점 최단 경로]

* Dijkstra's Algorithm (다익스트라 알고리즘) (URL)

Examples where Optimal Solution is not guaranteed with Greedy Algorithms

(그리디 알고리즘으로 최적해가 보장되지 않는 예시)

- 그리디 알고리즘은 대부분의 경우에서 최적해를 보장하지 못한다.

Path for Optimal Sum in Binary Tree Problem (이진 트리의 최적합 경로 문제)

- 각각의 노드가 Positive Weighted Node로 구성된 이진 트리에서,

루트에서 임의의 리프 노드까지의 경로들 중, 가중치의 합이 최대인 경로를 계산하는 문제이다.

- 이 때, 가중치는 Parent에서 왼쪽, 오른쪽 분기여부를 결정짓는 요인이 아니다.

(즉, 가중치와 노드의 Key는 다른 개념이라 간주한다.)

- 그러므로, Parent에 다다라서야 Child의 가중치 값을 확인할 수 있다.

(직관적으로, Greedy 알고리즘처럼 그 때마다 최선책을 골라가는 방법으로는 최적해를 찾을 수 없음을 알 수 있다.)

- 즉, DFS와 같은 Backtracking 탐색을 통해 최적해를 계산해내야 하고,

이에 대한 수행 시간의 상한은 트리의 노드의 개수에 비례할 것이다.

Knapsack Problem (보따리 문제)

Coin Exchange Problem (동전 바꾸기 문제)

Examples where Optimal Solution is guaranteed with Greedy Algorithms

(그리디 알고리즘으로 최적해가 보장되는 예시)

- 드물지만, 그리디 알고리즘이 최적해를 도출해낼 수 있는 경우가 있다.

Minimum Spanning Tree (최소 신장 트리)

Dijkstra's Shortest Path Algorithm (다익스트라 최단 경로 알고리즘)

Meeting Room Allocation Problem (회의실 배정 문제)

Matroid Structure (매트로이드 공간 구조)

Reference: Introduction to Algorithms 3E (CLRS)

(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘

(문병로 저, 한빛아카데미, 2018)

728x90

from http://dad-rock.tistory.com/663 by ccl(A) rewrite - 2021-08-30 14:00:28