💰 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)
: "매 선택에서 지금 이 순간 당장 최적의 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법
- 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제에 접근한다는 점에서 정렬(Sort)기번이 함께 이용되는 경우가 많다.
그리디 알고리즘의 장점 🙆
: 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한 '특정한 상황'에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있다.
💬 그리디 알고리즘 예시
620원이 있다면, 620원 이하의 가장 큰 액수가 500원짜리이므로 먼저 500원짜리 동전을 하나 사용하고, 120원이 남는다. 이제 500원짜리는 못 쓴다. 대신 그 다음으로 큰 100원짜리를 사용할 수 있다. 그리고 남은 20원은 10원짜리 2개를 사용할 수밖에 없고 이렇게 하면 답은 동전 4개가 된다.
성립하는 이유?
500, 100, 50, 10원짜리 동전들을 이렇게 정렬해 놓고 보면, 반드시 큰 쪽은 작은 쪽 액수의 배수이다. 따라서 큰 금액의 동전을 자신의 약수인 더 작은 여러 개의 동전들로 교체하면 동전 개수가 반드시 늘어나지만, 반대로 작은 동전들이 많이 있다면 이걸 모아 큰 동전 액수를 만들 수 있다면 무조건 바꾸는 게 동전 개수를 줄일 수 있기에 이득이다.
저 배수라는 성질이 성립하지 않으면 이 성질도 깨지고, 그리디 알고리즘도 더이상 사용할 수 없다.
근사 알고리즘 🌊
그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만, 어느정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기때문에 실용적으로 사용이 가능하다. 허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다. 또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.
[JAVA] 백준 알고리즘 4796번 문제 풀이 (캠핑)
https://sanizzang.tistory.com/6
[JAVA] 백준 알고리즘 1449번 문제 풀이 (수리공 환승)
https://sanizzang.tistory.com/7
