바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 대부분의 경우 뛰어난 결과를 도출하지는 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다는 점에서 매우 유용한 알고리즘이다.
"""
배낭 문제
최대 15kg까지 담을 수 있는 배낭이 있고 각각 무게가 다른 짐들이 있다.
1kg 단위로 쪼갤수 있다.
12kg-$4 / 1kg-$2 / 4kg-$10 / 1kg-$1 / 2kg-$2
가격이 최대가 되도록 짐을 고르기
"""
cargo = [(4, 12), (2, 1), (10, 4), (1, 1), (2, 2)]
def fractional_knapsack(cargo):
capacity = 15
pack = []
for c in cargo:
pack.append((c[0] / c[1], c[0], c[1]))
pack.sort(reverse=True)
total_value: float = 0
for p in pack:
if capacity - p[2] >= 0:
capacity -= p[2]
total_value += p[1]
else:
fraction = capacity / p[2]
total_value += p[1] * fraction
break
return total_value
"""
주식 사고 팔기. 여러번의 거래로 낼 수 있는 최대의 이익 산출하기
ex)
주식그래프 : [7,1,5,3,6,4]
출력 : 7
"""
def maximum_benefit(prices):
result = 0
for i in range(len(prices)-1):
if prices[i+1] > prices[i]:
result += prices[i+1] - prices[i]
return result
# 파이썬스러운 방식
def maximum_benefit(prices):
return sum(max(prices[i+1]-prices[i], 0) for i in range(len(prices)-1))
출처 : 파이썬 알고리즘 인터뷰