참고 : 파이썬 알고리즘 인터뷰

그리디 알고리즘(greedy algorithm)

: 눈앞의 이익만을 좇는 알고리즘

예 ) 다익스트라 알고리즘(최단 경로 문제), 허프만 코딩(허프만 트리 빌드), 의사결정트리

최적해를 찾을 수 있는 조건 2가지

탐욕 선택 속성을 가진 최적 부분 구조인 문제들

탐욕 선택 속성 : 앞의 선택이 이후 선택에 영향을 주지 않는 것
최적 부분 구조 : 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우

배낭 문제

조합 최적화 분야의 매우 유명한 문제

배낭에 담을 수 있는 무게의 최댓값(15kg)이 정해져 있고 각각 짐의 가치와 무게 단위가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록, 즉 달러의 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제

짐을 쪼갤 수 있다면 -> 그리디 알고리즘
짐을 쪼갤 수 없다면 -> 다이나믹 프로그래밍

배낭 문제 - 짐 쪼갤 수 O -> 그리디

단가가 가장 높은 짐부터 채워나감
마지막 남은 짐은 쪼개서 배낭에 담는다.

(단가 계산 = 우선순위 결정 = 무게당 가격 = 가격/무게)

입력 : cargo = (가격/무게)튜플 형식의 리스트

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 = 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
   
    

동전 바꾸기 문제

이전 액면의 배수 이상이 되면 -> 그리디
배수가 안된다? -> 다이나믹 프로그래밍

각각의 동전 최대 활용법 : 가장 작은 동전 개수로 거슬러주면 됨

leetcode 122 - 주식 사고팔기

가격의 흐름이 인수로 주어지고, 저점에서 사고 고점에서 파는 것을 반복

def max_profit(prices):
	profit = 0
    
    for i in range(len(prices)-1):
    	if prices[i+1] >= prices[i]:
        	profit += prices[i+1] - prices[i]
    
    return profit