탐욕적 기법(Greedy Algorithm)
욕심쟁이 기법, 혹은 그리디라고 하는 이 기법은 항상 눈 앞의 가장 큰 이익만을 쫓는 방법입니다. 유명한 문제로는 도시락 데우기, 파일 합치기 등의 문제가 있습니다.
그리디 알고리즘으로 최적의 해를 구할 수 있는 문제는 한 번의 선택을 한 이후에도 원래 문제와 동일한 성징들이 성립하고 있습니다.
성질이 동일하게 보존되므로 동일한 전략을 계속 취해도 정답을 얻을 수 있습니다.
[예제 문제]를 생각하며 이해해보자.
문제 1. 동전
10원짜리, 50원짜리, 100원짜리, 500원짜리 동전을 사용해 어떤 금액을 표현하려 한다. 각 동전은 무수히 많은 대신, 동전 개수를 최소로 사용해야 한다면 어떻게 해야할까?
무조건 사용할 수 있는 한 가장 큰 금액의 동전을 많이 사용하면 된다는 것을 쉽게 떠올릴 수 있다.
왜 이 방법이 성립할까?
500, 100, 50, 10원짜리 동전들을 이렇게 정렬해 놓고 보면, 반드시 큰 쪽은 작은 쪽 액수의 배수이다. 따라서 큰 금액의 동전을 자신의 약수인 더 작은 동전들로 교체하면 동전 개수가 반드시 늘어나지만, 반대로 작은 동전을 많이 가지고 있다면 이걸 모아 큰 동전 액수를 만들 수 있다면 무조건 바꾸는 것이 동전 개수를 줄일 수 있기에 이득이다.
'배수'라는 성질이 성립하지 않으면 이 성질도 깨지고, 그리디 알고리즘도 더이상 사용할 수 없다.
만약 60, 50, 10원짜리 동전으로 가정해보자. 60은 50보다 크지만 50의 배수는 아니다. 이때 220원을 표현하려고 하면, 60원짜리부터 무작정 3개를 사용한다면 40원이 남는데 이건 10원짜리 4개로밖에 나타낼 수 없으므로 총 7개를 사용하게 된다. 그러나 답은 50원짜리 4개와 10원짜리 2개를 사용해 6개로 표현 가능하다.
문제 2. 분할가능 배낭
무게 제한이 50인 배낭에 3개의 물건을 넣어서 넣은 물건들의 가치 합이 최대가 되면 된다. 무게가 초과할 것 같으면 물건을 쪼개서 일부만 넣을 수 있다.
v는 물건의 가치, w는 무게, v/w는 무게 당 가치이다.
물건을 쪼갤 수 있다는 가정 하에서는 무엇부터 넣는 게 최선일까?
무게 대비 가치가 높은 것들을 먼저 넣는 게 좋을 것이다.
item = [[1, 60,10], [2, 100, 20], [3, 120, 30]]
def fractionalKnapsack(item, w):
# 무게 당 가치의 내림차순으로 정렬
sortedList = sorted(item, key=lambda x: -(x[1]/x[2]))
limit = w
result = 0
for it in sortedList:
cur = it
if limit > 0:
if limit >= cur[2]:
limit -= cur[2]
result += cur[1]
else:
result += (cur[1] / cur[2]) * limit
limit = 0
else:
break
return int(result)
print(fractionalKnapsack(item, 50)) # 240무게 제한 50에 물건은 1, 2, 3순서로 넣게 된다. 3번은 무게 초과이기 때문에 20만큼만 쪼개서 넣으면 된다.
[백준 추천문제]
4796(캠핑)
1449(수리공 항승)
175090(And the Winner is.. Ourselves!)
11047(동전 0)
1931(회의실배정)
11000(강의실 배정)
1700(멀티탭 스케줄링)
2212(센서)
13904(과제 ★)
15748(Rest Stops ★)
1493(박스 채우기 ★)
[참고]
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220775134486&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList
https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
