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

 

✅ Greedy Algorithm 

"매 선택에서 지금 이 순간 당장 최적의 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가진 알고리즘

• 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등 극단적으로 문제에 접근해야 한다는 점에서 정렬(Sort)이 함께 이용되는 경우가 많다.

 

 Greedy Algorithm 장점

항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다.

또한 특정한 상황에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수 있다.

 

> 예시

620원이 있다면, 620원 이하의 가장 큰 액수가 500원짜리이므로 먼저 500원짜리 동전을 하나 사용하고, 120원이 남는다. 이제 500원짜리는 못 쓴다. 대신 그 다음으로 큰 100원짜리를 사용할 수 있다. 그리고 남은 20원은 10원짜리 2개를 사용할 수 밖에 없고, 이렇게 하면 답은 동전 4개가 된다.

성립하는 이유
500, 100, 50, 10원짜리 동전들을 이렇게 정렬해 놓고 보면, 반드시 큰 쪽은 작은 쪽 액수의 배수이다.
따라서 큰 금액의 동전을 자신의 약수인 더 작은 여러 개의 동전들로 교체하면 동전 개수가 반드시 늘어나지만, 반대로 작은 동전들이 많이 있다면 이걸 모아 큰 동적 액수를 만들 수 있다면 무조건 바꾸는게 동전 개수를 줄일 수 있기에 이득이다.
저 배수라는 성질이 성립하지 않으면 이 성질도 깨지고, 그리디 알고리즘도 더 이상 사용할 수 없다. 

 

 

그리디 알고리즘의 더 자세한 이해와 내용, 문제를 통한 내용은 Stranger's LAB 님의 포스팅을 참고해보자.
https://st-lab.tistory.com/143