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

알고리즘

0_TLS 2025. 2. 1. 22:31

최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론

각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종 해답에 도달하는 알고리즘이다.

-> 이때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값에 '근사한 값'을 목표로 한다.

1. 탐욕스러운 선택 조건

- 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. 여기서 '안전하다' 라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.

2. 최적 부분 구조 조건

- 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이라는 조건

- 즉, 전체 문제 안에 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출돼야 한다는 것.

참고. 그리디 알고리즘과 동적 계획법 비교

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

recoding;