[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

1. 탐욕 알고리즘 이란?

• Greedy algorithm 또는 탐욕 알고리즘이라고 불림
• 최적의 해에 가까운 값을 구하기 위해 사용됨
• 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

 

2. 그리디 알고리즘으로 정답을 찾는 조건

 

1.  탐욕스러운 선택 조건(greedy choice proeprty)

2.  최적 부분 구조 조건(optimal substructure)

 

- 매번 탐욕스러운 선택을 해야 하며, 각각의 부분의 최적이 영원히 최적이 여야 한다.왜냐하면 그럴 경우 앞으로도 최적인 게 자명하기 때문이다.

즉, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

 

 

 

3. 탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용

• 반드시 최적의 해를 구할 수 있는 것은 아니기 때문

• 최적의 해에 가까운 값을 구하는 방법 중의 하나임

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

 

그리디 알고리즘에 따르면 매번 큰 값을 선택하면 4 - 9 - 12가 된다. 이것은 실제 최대 값이 아니라는 것을 알 수 있다. 실제로는 4 - 1 - 99를 따라가야 최대를 구할 수 있기 때문이다. 이처럼 그리디는 항상 그 상황에서는 최적이지만 종합적으로는 최적의 값을 도출하지 않는 경우가 발생한다.