📌 Greedy Algorithm

최댓값을 구하는 과정을 최적의 선택 / 그리디한 선택으로 나누어서 보여주고 있다.

각 단계에서 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다. 항상 최적의 값을 보장하는 것이 아니라 최적의 값에 `근사한 값`을 목표로 한다. 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구하고 이를 결합하여 전체 문제의 최적해를 구하는 경우에 사용된다.

💿 보장 조건

1. 탐욕적 선택 속성 (Greedy Choice Property) : 이전의 선택이 이후의 선택에 영향을 주지 않아야 한다.
2. 최적 부분 구조 (Optimal Substructure) : 전체 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해여야 한다.

해당 조건들을 만족하지 못하는 경우에도 그리디 알고리즘은 근사 알고리즘 으로 사용할 수 있다.
이러한 경우에도 어느정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.
매트로이드 라는 특별한 구조가 있는 문제에 대해서는 그리디 알고리즘이 언제나 최적해를 찾아낼 수 있다.

💿 단계

1. 선택 절차

현재 상태에서 최적인 선택지를 선택한다.
해당 선택을 이후에 바뀌지 않는다.

2. 적절성 검사

선택한 항목이 문제의 조건을 만족시키는지 확인한다.
조건을 만족시키지 않으면 해당 항목을 제외핟ㄴ다.

3. 해답 검사

모든 선택이 완료되면, 최종 선택이 문제의 조건을 만족시키는지 확인한다.

💿 장/단점

장점

1. 직관적이고 이해하기 쉬워 구현이 간단하다.
2. 매 단계에서 최적의 선택을 하기 때문에 계산 속도가 빠르다.

단점

1. 항상 최적해를 보장하지 않는다.

💿 DP (Dynamic Programming) 와의 차이점?

	Greedy Algorithm	Dynamic Programming
설명	각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방법	작은 문제의 해를 메모제이션(Memoization) 하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식
성립 조건	1. 탐욕 선택 속성 (Greedy Choice Property) 2. 최적 문제 구조 (Optimal Substructure)	1. 중복 부분 문제 (Overlapping Subproblems) 2. 최적 부분 구조 (Optimal Substructure)
중복 부분 문제	해결하지 않는다.	해결 가능하다.
상황	각 단계의 상황에서 최적을 선택하여 최적의 경로를 구한다. 최적이 아닌 경우가 될 수 있거나 풀리지 않는 문제가 될 수 있다.	모든 상황을 계산하여 최적의 경로를 구할 수 있다. 모든 상황을 계산하기 때문에 시간이 오래 걸린다.

---

이미지 출처

모든 이미지 출처