알고리즘 / 그리디 알고리즘(탐욕 알고리즘)

그리디 알고리즘이란?

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

 

그리디 알고리즘을 활용한 문제들이다.

 

장점

• 계산 속도가 매우 빠르다.
• Dynamic programming 및 다른 알고리즘보다 빠른 속도로 최적해를 도출할 수 있다. 
• 그리디 알고리즘을 적용할 수 있는 문제 유형에 대해 이해한다면 효율적으로 최적해를 찾을 수 있다. 
• 이게 무슨 말인지 몰라서 예시를 들어서 설명해보겠다.

 

예시

위 그림은 그리디 알고리즘에 대해서 나타낸 것이다. 

 

제일 위 4에서부터 시작하며, 큰 수를 찾아낸다.

그리디 알고리즘에서는  순간순간마다 최적인 해를 찾으므로 4보다 큰 수인 9, 9보다 큰 수인 12를 찾게 된다. 하지만 실제 가장 큰 수는 99이다. 이처럼 그리디 알고리즘에서는 전체 문제 해결에서의 최적 해답을 찾지는 못한다. 매번 최선의 결정을 하지만 그것이 언제나 문제 전체의 최적이 되지는 않는다. 

 

 

---

 

그리디 알고리즘 문제 조건

• greedy choice property(탐욕스러운 선택 조건) : 현재 선택이 이 후의 선택에 영향을 주지 않는다.
• optimal substructure(최적 부분 구조 조건) : 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 한다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다. 

 

 

예시 - 백준 11047 : 동전 0

www.acmicpc.net/problem/11047

11047번: 동전 0

사용되는 동전의 수가 최소가 되어야한다. 그때 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현한다. 큰 금액부터 남은 금액을 최대로 채울 수 있는 개수를 선택한다. 

greedy choice property : 현재 금액의 선택이 이후 선택에 관계없이 금액을 최대로 개수를 선택하기 때문에 현재 선택이 이후의 선택에 영향을 주지 않는다. 

optimal substructure : 큰 값부터 먼저 선택권을 부여하기 때문에 매 순간 나머지 금액을 최대로 채우는 선택이 결국 가장 최소의 동전 개수를 도출한다. 

 

---

참고 

그림 - covenant.tistory.com/131

그림 - velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5

참고 - https://it-college-diary.tistory.com/entry/21-Greedy-Algorithm탐욕 법-욕심쟁이-알고리즘-개념