알고리즘 혁신의 종류에 대하여 구체적으로 설명하시오

Ⅰ. 서론

그리디 알고리즘(Greedy Algorithm)은 최적해를 구하기 위해 활용하는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때, ‘탐욕’이란 뜻처럼 가장 최적의 해만을 선택하는 과정으로 최종적인 해답에 도달한다. 그리디 알고리즘이 순간마다 지역적으로 하는 선택은 최적이라 할 수 있지만, 그 선택들이 모인 최종적(전역적)인 해답은 최적화되었다고 보장할 수 없다. 이에 본 과제에서는 그리디 알고리즘의 최적화 경우와 그렇지 않은 경우를 알고리즘 예시를 들어 설명해 보도록 하겠다.
Ⅱ. 본론
1. 그리디 알고리즘의 최적화 결과
(1) 사례 제시
그리디 알고리즘이 최적화 알고리즘이 될 수 있는 사례는 거스름돈 문제로 설명할 수 있다. 거스름돈 문제는 거스름돈으로 사용할 수 있는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하고 물건을 산 손님에게 줄 거스름돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하는 문제이다.
그리디 알고리즘으로 동전의 개수를 구하는 과정은 일반적으로 가장 큰 화폐 단위 동전부터 돈을 선택해 거슬러 주는 방법과 동일하다. 가장 먼저 500원짜리 동전을 거슬러 줄 수 있을 …