[알고리즘] 그리디 - JavaScript

그리디? 

매 선택에서 지금 순간 가장 최적인 답을 선택하는 알고리즘이다. 

A에서 F로 이동할 때 전체 코스트로만 본다면 D로 가는 것이 더 빠르다. 

하지만 그리디를 적용한다면 A 의 시점으로만 봤을 때는 B로 가는 것이 더 빠르기 때문에 B로 이동하게 된다. 

 

이처럼 현재 시점의 최적의 답은 선택하지만 이것이 최적의 결과를 보장하지는 않는다. 

그리디의 특징

• 보통 최적의 결과를 구하는 알고리즘보다 빠른 경우가 많다. 
• 크루스칼, 다익스트라 알고리즘 등에 사용된다. 
• 직관적인 문제를 풀 때 적합하다. 

사용되는 방식

동전 반환 문제로, 

큰 단위인 지폐, 동전 순으로 거스름돈을 만들 때 사용한다. 

1860원을 먼저 가장 큰 단위인 1000원짜리 지폐로, 그 후 500원, 100원, 50원, 10원 순으로 구하면 

빠르게 계산이 가능하다.