개발새발 로그

그리디 알고리즘은 "지금 당장 눈앞에 보이는 최적의 상황만을 쫒는 알고리즘"이다. 그리디 알고르짐은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있습니다. 또한 특정한 상황에는 그리디 알고리즘이 최적의 해를 구할 수도 있습니다. 예제로 거스름돈 문제를 풀어보겠습니다. 예를 들어 670원을 걸러줘야하는 상황입니다. 이는 10원짜리 67개보다 500원짜리 1개 50원짜리 1개 10원짜리 1개를 주는 것이 총 3개로 더 효율적입니다. 따라서 이 경우 "무조건 더 큰 화폐 단위부터 거슬러준다"라는 알고리즘만 지키면 최적의 해를 구할 수 있습니다. 이러한 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, ..