루피

그리디 알고리즘이란? 그리디 알고리즘은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 결과를 도출하는 기법이다. 그리디 알고리즘은 지금 당장의 상황만을 고려하면 되기에 편리하다. 하지만 매 선택의 순간에서의 최적이 종합적 측면에서의 최적을 보장하지는 않기에 주의를 해야한다. 또한 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 못하는 경우가 많다. 따라서 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요하다. 편의점에서 손님이 물건을 사고 값을 지불하였을 때 N원의 돈을 거슬러 줘야한다. 그럼 이 N을 거슬러 줄 때 사용할 수 있는 동전의 최소 개수는 몇 개일까? (N은 10의 배수이며 동전은 500원, 100원, 50원, 10원짜리이다.) >> 최적의 ..