[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)

💡탐욕 알고리즘

 - 최적해를 구하는 데에 사용되는 근사적인 방법 (여러 경우 중 하나를 결정해야 할 때 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식)

 - 그 순간의 선택은 지역적으론 최적이지만 전체적으로 봤을 땐 아닐 수 있음

     ‼️ 탐욕 알고리즘을 적용할 수 있는 문제의 경우, 지역적으로 최적이면 전역적으로도 최적

 

💡 문제 해결 방법

1) 선택 절차: 현재 상태에서 최적의 해답 선택

2) 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사

3) 해답 검사: 원래의 문제가 해결되었는지 검사 후, 해결되지 않았으면 선택 절차로 돌아감

 

 

✔️ 거스름돈 계산하기 문제

 - 동전의 개수가 최소가 되도록 거스름 돈을 내는 방법

 - 가치가 높은 동전부터 x가 초과되지 않도록 계속 냄

 

while(동전이 남아있고 or 문제 미해결){

	//가장 가치있는 동전 (선택)
    if(거슬러줘야 하는 돈<거스름돈 총액){ //적절성 검사
    	//동전 다시 넣음
    else{
    	거스름돈에 동전 넣음
    }
    
    if(거스름돈 총액 == 거슬러줘야 하는 돈){ //해답점검
   		문제해결
    }
}

ex) 12원짜리 동전이 있다고 가정했을 때, 거스름돈 16원을 내기 위해 그리디 알고리즘을 쓰면

     전체적으로 봤을 땐 최적X

 

 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬