목록그리디 (1)

모종닷컴

[알고리즘]그리디 알고리즘

그리디 알고리즘 : 최적화 문제(가능한 해들 중 가장 좋은 해를 고르는)를 해결하는 알고리즘 ◆그리디 알고리즘의 특징 1)데이터 간의 관계를 고려하지 않고 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다. 2)일단 한번 선택하면 그 데이터를 버리고 다른 것을 취하지 않는다. ◆그리디 알고리즘으로 해결 가능한 대표적인 문제들 1)동전 거스름돈 :거스름돈을 받을 때 가장 적은 수의 동전으로 주는 문제 #유사코드 입력:거스름돈 액수W 출력:거스름돈 액수에 대한 최소 동전 수 change=W,n500=n100=n10=n1=0 //n500,n100,n50,n10,n1은 각각의 동전 수를 위한 변수이다. while(change>=500) change=change-500,n500++ while(chan..
3학년/알고리즘 2017. 10. 2. 10:56
이전 Prev 1 Next 다음