그리디 알고리즘의 수학적 정당성

DP: 모든 경우 시도 → 최적
그리디: 매 단계 최선 → 빠름

그리디가 최적 보장하려면:
1. 그리디 선택 속성 (Greedy Choice Property)
   현재 최선이 전체 최선의 일부
2. 최적 부분 구조 (Optimal Substructure)
   DP와 공통

# 동전 [500, 100, 50, 10] — 그리디 최적
def coin_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        while amount >= c:
            amount -= c
            result.append(c)
    return result


print(coin_greedy([500, 100, 50, 10], 760))
# [500, 100, 100, 50, 10]
# 5개 동전 — 최적


# 그리디 최적인 이유:
# 큰 단위가 작은 단위의 배수 (500 = 5*100, 100 = 2*50, 50 = 5*10)
# → 큰 단위 사용이 항상 손해 없음

# 동전 [4, 3, 1]로 6 만들기
# 그리디: 4 + 1 + 1 = 3개
# 최적: 3 + 3 = 2개 ← DP로만 발견

def coin_dp(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], dp[a-c] + 1)
    return dp[amount]


print(coin_greedy([4, 3, 1], 6))  # [4, 1, 1] = 3개
print(coin_dp([4, 3, 1], 6))      # 2개 (3+3)

# 한국 동전은 그리디 OK — 일반 동전 시스템은 DP 필요

# 시간 겹치지 않게 최대한 많은 활동 참가
# 그리디: 끝나는 시간이 빠른 순

activities = [
    ('아침회의', 9, 11),
    ('점심',    12, 13),
    ('워크샵',  10, 14),
    ('미팅A',   13, 14),
    ('미팅B',   13, 16),
    ('저녁',    18, 20),
]


def activity_selection(activities):
    # 끝나는 시간 기준 정렬
    sorted_acts = sorted(activities, key=lambda x: x[2])

    selected = []
    current_end = 0

    for name, start, end in sorted_acts:
        if start >= current_end:
            selected.append((name, start, end))
            current_end = end

    return selected


for act in activity_selection(activities):
    print(act)
# ('아침회의', 9, 11)
# ('점심', 12, 13)
# ('미팅A', 13, 14)
# ('저녁', 18, 20)
# 4개 활동 — 최적


# 그리디 최적성 증명:
# 끝이 가장 빠른 활동을 선택해도 손해 없음
# → 다른 활동을 더 많이 추가할 수 있는 선택지를 남김

# 빈도 높은 문자에 짧은 비트 할당 → 압축률 최대
# 그리디: 가장 빈도 낮은 두 노드를 합치며 트리 구성

import heapq
from collections import Counter

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq


def build_huffman(text):
    freq = Counter(text)
    heap = [Node(char, f) for char, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    return heap[0]


def get_codes(node, prefix='', codes=None):
    if codes is None:
        codes = {}
    if node.char is not None:
        codes[node.char] = prefix or '0'
    else:
        get_codes(node.left, prefix + '0', codes)
        get_codes(node.right, prefix + '1', codes)
    return codes


text = "abracadabra"
root = build_huffman(text)
codes = get_codes(root)
print(codes)
# 빈도 높은 'a'에 짧은 비트, 낮은 빈도 문자에 긴 비트

그리디 적용 가능?
□ 그리디 선택 속성 증명 가능?
□ 최적 부분 구조?
□ 작은 케이스로 그리디 실패 사례 없는지 확인

위 3개 모두 ✅면 그리디 (빠름)
하나라도 ❌면 DP (정확)

# 0-1 배낭은 DP, 분할 가능 배낭은 그리디
# 분할 가능: 물건을 부분만 가져갈 수 있음

def fractional_knapsack(items, capacity):
    """
    items: [(value, weight), ...]
    가치/무게 비율 높은 순으로 그리디
    """
    sorted_items = sorted(items, key=lambda x: -x[0]/x[1])

    total_value = 0
    for value, weight in sorted_items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            # 부분만 가져가기
            total_value += value * (capacity / weight)
            break

    return total_value


items = [(60, 10), (100, 20), (120, 30)]
print(fractional_knapsack(items, 50))
# 60 (item1 전체) + 100 (item2 전체) + 120 * (20/30) = 240