그리디알고리즘

탐욕 알고리즘(그리디 알고리즘) 탐욕 알고리즘 또는 그리디 알고리즘 이라는 것에 대해서 이야기 해봅시다. 탐욕 알고리즘은 주어진 순간 순간마다 가장 최선의 선택을 하는 알고리즘 설계 기법입니다. 매 순간마다 하는 선택은 최선이지만, 전체로 봤을 때는 최적의 선택이라는 보장을 하지는 않습니다. 그리디 알고리즘이 제대로 동작하지 않은 예시로 주로 드는 것은 마쉬멜로우 실험입니다. 예를 들어서, 지금 당장에 마쉬멜로우 1개를 받을 수 있지만, 10분을 기다린 경우 2개의 마쉬멜로우를 받을 수 있는 실험이 있다고 가정해 봅시다. 그리디 알고리즘으로는 지금 당장 1개를 선택하겠지만, 전체로 본다면 10분을 기다린 후에 2개의 마쉬멜로우를 받는게 가장 많은 마쉬멜로우를 받을 수 있을 것 입니다. 그리디 알고리즘은 ..

문제 링크 : www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 관련 알고리즘 : 그리디 알고리즘(탐욕 알고리즘), 동적 계획법 아이디어) 2가지 방법으로 풀어봤다. 그리디) 처음 설탕을 가져갈 때 5kg짜리로 최대한 많이 담고, 남은 설탕을 3kg으로 가져감. 만약 5kg으로 최대한 담고 3kg으로 나머지를 담는데, 나눠떨어지지 않으면 5kg를 하나 빼고 다시 3kg을 담음. 5kg를 다 뺐지만, 3kg만으로 설탕이 나눠지지 않으면, -1을 출력. 동적 계획법)cach..