'2016/09/09'에 해당되는 글 1건

  1. 2016.09.09 Greedy Algorithm 과 거스름돈 예제
반응형

 탐욕 알고리즘은 각 단계의 부분 문제를 풀때 근시안적으로 최적해를 구한다고 해서 붙여진 것이다. 동적 계획법은 최적의 해를 구하긴 하지만 탐욕 알고리즘보다는 더 많은 연산을 요구한다. 탐욕 알고리즘은 동적 계획법과는 달리 최적의 해를 구해준다는 보장을 하지 못한다.


 탐욕 알고리즘은 동적 계획법처럼 대상 문제가 최적 부분 구조를 갖고 있어야 한다. 탐욕 알고리즘은 다음과 같이 동작한다.

 1) 해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다.

 2) 실행 가능성 검사: 새로운 부분해 집합이 실행가능한지 확인한다. (문제의 제약 조건을 위반하는지 검사한다)

 3) 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 전체 문제의 해가 완성되지 않았다면 1) 부터 다시 시작한다.


 거스름돈 줄이는 것에 탐욕 알고리즘을 적용할 수 있다.

 1) 해 선택: 현재 고를 수 있는 가장 단위가 큰 동전을 하나 고른다.

 2) 실행 가능성 검사: 1)에서 고른 동전 단위를 잔돈에서 뺸다. 뺀 값이 0보다 작으면 고를수 있는 동전에서 이 동전을 뺴고 1)부터 다시 시작한다. 0보다 크면 2)를 계속한다.

 3) 해 검사: 차감된 거스름돈이 0이 되는지 검사한다. 0 보다 크면 1)로 돌아가서 거스름돈에 추가할 동전을 고른다.




코드를 실행하고 다음을 입력해 보자

5

500

100

50

10

1

800


동전종류가 500, 100, 50, 10, 1 의 5가지이고 800원에 대해서 최소 동전을 출력한다. 

500

100

100

100

이 출력될 것이다.


Greedy 알고리즘은 최적해를 구해주지 않는다. 예를 들어 

5

500

400

100

50

800


을 입력하면 

500

100

100

100

이 출력된다. 최적값은

400

400


이 출력되야 하는 것인데 정확하게 해를 구하지 못한다. 그래서 근시안적 알고리즘이 되는 것이다. 정확한 해를 구하기 위해서는 동적프로그래밍 기법을 사용해야 한다.

반응형
Posted by alias
,