TIL#116 그리디 알고리즘

Dasom·2020년 12월 6일
0

자료구조

목록 보기
7/8

그리디 알고리즘(Greedy Algorithm)

바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 대부분의 경우 뛰어난 결과를 도출하지는 못하지만, 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 합리적인 시간 내에 최적에 가까운 답을 찾을 수 있다는 점에서 매우 유용한 알고리즘이다.

  • 탐욕 선택 속성(Greedy Choice Property)
    : 앞의 선택이 이후 선택에 영향을 주지 않는 것. 선택을 다시 고려하지 않음
  • 최적 부분 구조(Optimal Substructure)
    : 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우
"""
배낭 문제 
최대 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))





출처 : 파이썬 알고리즘 인터뷰

profile
개발자꿈나무🌲

0개의 댓글