[컴퓨터 알고리즘]알고리즘 연습문제 4장

소개글

도움이 되셨으면 합니다

목차

1. 탐욕적인 방법을 사용하면 항상 거스름돈 문제의 최적 해를 구할 수 있음을 보여라.
2. 프림알고리즘(알고리즘4.1)을 이용하여 다음 그래프의 최소비용 신장 트리를 구하라. 그리고 수행되는 절차를 단계별로 보여라.
4.프림 알고리즘을 구현하는 프로그램을 작성하라.
6. 크루스칼 알고리즘을 사용하여 연습문제 2의 그래프의 최소비용신장트리를 구하고, 수행되는 절차를 단계별로 구하라.
11. 다익스트라 알고리즘을 사용하여 연습문제 2의 그래프에서 정점 V4에서 다른 모든 정점으로 가는 최단 경로를 구하라. 그리고 수행되는 절차를 단계별로 구하라.

본문내용

1. 탐욕적인 방법을 사용하면 항상 거스름돈 문제의 최적 해를 구할 수 있음을 보여라.

탐욕적인 알고리즘의 설계절차는
1.선정과정 2. 적정성 점검 3. 해답점검으로 이루어지는데
거스름돈 문제의 경우 우리나라는 1000원, 500원, 100원,50원,10원 으로 거스름돈을 준다.
만약 850원의 거스름돈이라면
1.선정과정- 가장 큰 거스름돈은 500원이다. 그 후 100원짜리 3개, 50원짜리 1개이다.
2.적정성점검- 거스름돈으로 줄 동전의 개수는 5개이다.
3.해답점검- 다른 해로, 100원 8개와 50원 1개 총 9개, 50원짜리 17개, 10원짜리 85개라는 해가 있으나 최적은 아니다.
만약, 120원이나 370원등의 10과 50을 공약수로 갖지 않는 거스름돈이 출현할 경우는 이 알고리즘은 항상 최적이 될 수 없다. 다만, 우리나라 거스름돈은 늘 10과 50을 공약수로 가지므로 항상 성립한다.

참고 자료

없음