그리디 알고리즘
그리디 알고리즘
그리디 알고리즘
그리디 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불리기도 한다.
데이터 간의 관계를 고려하지 않고 수행과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 -> ‘근시안적’인 선택
EX )
동전 거스름돈 문제
남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것
CoinChange 의사코드(입력: 거스름돈 액수 W, 출력: 거스름돈 액수에 대한 최소 동전 수)
- change=W, n500=n100=n50=n10=n1=0
- while ( change ≥ 500 )
change = change-500, n500++ - while ( change ≥ 100 )
change = change-100, n100++ - while ( change ≥ 50 )
change = change-50, n50++ - while ( change ≥ 10 )
change = change-10, n10++ - while ( change ≥ 1 )
change = change-1, n1++ - return (n500+n100+n50+n10+n1)
