목록동전 거스름돈 문제 (1)

YJ_Scribbles

03_그리디알고리즘

★ 그리디 알고리즘 - 최적화 문제를 해결하는 알고리즘 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 ㅇ 최적화 (optimization) 문제 - 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 ㅇ 특징 - 데이터 간의 관계를 고려하지 않고 수행 과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 (‘근시안적’인 선택) - 일단 한 번 선택하면, 이를 절대로 번복하지 않음 -> 매우 단순하며, 또한 제한적인 문제들만 해결 가능 ★ 예시1. 동전 거스름돈 문제 - 남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것 ㅇ 알고리즘 -> CoinChange 알고리즘은 항상 최적의 답을 주지 못함 (따라서 실제로는 거스름돈에 대한 그리디 ..
이론_전공/알고리즘 2020. 10. 14. 15:15
이전 Prev 1 Next 다음