그리디 알고리즘 완벽 정리 – 활동 선택, 회의실 배정 등 코딩테스트 필수 유형 풀이

def activity_selection(activities):
    """
    활동 선택 문제: 최대한 많은 활동을 선택한다.
    activities: [(시작시간, 종료시간), ...]
    반환: 선택된 활동 리스트
    """
    # 1단계: 종료 시간 기준으로 오름차순 정렬
    sorted_acts = sorted(activities, key=lambda x: x[1])

    selected = [sorted_acts[0]]  # 첫 번째 활동은 무조건 선택
    last_end = sorted_acts[0][1]  # 마지막으로 선택한 활동의 종료 시간

    # 2단계: 나머지 활동을 순회하며 선택 가능한 것만 추가
    for start, end in sorted_acts[1:]:
        if start >= last_end:  # 시작 시간이 마지막 종료 시간 이후면 선택
            selected.append((start, end))
            last_end = end  # 종료 시간 갱신

    return selected


# 예제 실행
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
              (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"선택된 활동 수: {len(result)}")
print(f"선택된 활동: {result}")

def max_meetings_one_room(meetings):
    """
    하나의 회의실에서 최대한 많은 회의를 배정한다.
    meetings: [(시작, 종료), ...]
    """
    # 종료 시간 기준 정렬 (활동 선택과 동일)
    sorted_meetings = sorted(meetings, key=lambda x: x[1])

    count = 1
    last_end = sorted_meetings[0][1]

    for start, end in sorted_meetings[1:]:
        if start >= last_end:
            count += 1
            last_end = end

    return count


# 예제: 백준 1931번 스타일
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
            (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(f"최대 회의 수: {max_meetings_one_room(meetings)}")  # 4

import heapq

def min_meeting_rooms(meetings):
    """
    모든 회의를 배정하기 위한 최소 회의실 개수를 구한다.
    meetings: [(시작, 종료), ...]
    """
    if not meetings:
        return 0

    # 1단계: 시작 시간 기준으로 정렬
    sorted_meetings = sorted(meetings, key=lambda x: x[0])

    # 2단계: 최소 힙으로 각 회의실의 종료 시간 관리
    # 힙에는 현재 사용 중인 회의실의 종료 시간이 들어간다
    rooms = []  # min-heap of end times
    heapq.heappush(rooms, sorted_meetings[0][1])

    for start, end in sorted_meetings[1:]:
        # 가장 빨리 끝나는 회의실이 현재 회의 시작 전에 끝나면 재활용
        if rooms[0] <= start:
            heapq.heappop(rooms)  # 기존 회의실 제거

        # 새 회의의 종료 시간을 힙에 추가 (재활용이든 신규든)
        heapq.heappush(rooms, end)

    # 힙의 크기 = 필요한 회의실 수
    return len(rooms)


# 예제 실행
meetings = [(0, 30), (5, 10), (15, 20)]
print(f"최소 회의실 수: {min_meeting_rooms(meetings)}")  # 2

meetings2 = [(1, 3), (2, 4), (3, 5)]
print(f"최소 회의실 수: {min_meeting_rooms(meetings2)}")  # 2

def min_meeting_rooms_sweep(meetings):
    """
    스위핑 기법으로 최소 회의실 수를 구한다.
    시작 시점에 +1, 종료 시점에 -1을 하여 동시 진행 최대값을 구한다.
    """
    events = []
    for start, end in meetings:
        events.append((start, 1))   # 회의 시작: +1
        events.append((end, -1))    # 회의 종료: -1

    # 시간순 정렬 (같은 시간이면 종료(-1)를 먼저 처리)
    # -1 < 1이므로 자동으로 종료가 먼저 정렬됨
    events.sort()

    max_rooms = 0
    current_rooms = 0

    for time, delta in events:
        current_rooms += delta
        max_rooms = max(max_rooms, current_rooms)

    return max_rooms


# 검증
print(min_meeting_rooms_sweep([(0, 30), (5, 10), (15, 20)]))  # 2

def fractional_knapsack(capacity, items):
    """
    분할 가능 배낭 문제를 그리디로 풀기.
    capacity: 배낭 용량
    items: [(무게, 가치), ...]
    반환: (최대 가치, 선택 내역)
    """
    # 1단계: 단위 무게당 가치 기준 내림차순 정렬
    sorted_items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0
    remaining = capacity
    selection = []  # (물건 인덱스, 비율)

    for weight, value in sorted_items:
        if remaining <= 0:
            break

        if weight <= remaining:
            # 물건 전체를 넣을 수 있는 경우
            total_value += value
            remaining -= weight
            selection.append((weight, value, 1.0))  # 100% 선택
        else:
            # 남은 용량만큼만 쪼개서 넣기
            fraction = remaining / weight
            total_value += value * fraction
            selection.append((weight, value, fraction))
            remaining = 0

    return total_value, selection


# 예제 실행
items = [(10, 60), (20, 100), (30, 120)]  # (무게, 가치)
capacity = 50

max_value, selection = fractional_knapsack(capacity, items)
print(f"최대 가치: {max_value}")
print("선택 내역:")
for w, v, frac in selection:
    print(f"  무게 {w}, 가치 {v} → {frac*100:.0f}% 선택 (획득 가치: {v*frac:.1f})")

def min_coins_greedy(amount, coins):
    """
    그리디로 최소 동전 개수를 구한다.
    동전이 서로의 배수일 때만 정당한 결과를 보장한다.
    """
    # 큰 단위부터 정렬
    coins_desc = sorted(coins, reverse=True)

    total_count = 0
    breakdown = []  # 각 동전별 사용 개수
    remaining = amount

    for coin in coins_desc:
        if remaining <= 0:
            break
        count = remaining // coin  # 해당 동전을 최대한 사용
        if count > 0:
            breakdown.append((coin, count))
            total_count += count
            remaining -= coin * count

    return total_count, breakdown


# 예제: 백준 11047번 (동전 0)
coins = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
amount = 4790

count, breakdown = min_coins_greedy(amount, coins)
print(f"{amount}원을 만드는 최소 동전 수: {count}개")
for coin, cnt in breakdown:
    print(f"  {coin}원 × {cnt}개")

4790원을 만드는 최소 동전 수: 12개
  1000원 × 4개
  500원 × 1개
  100원 × 2개
  50원 × 1개
  10원 × 4개

# 그리디가 실패하는 예시
def min_coins_dp(amount, coins):
    """DP로 최소 동전 개수를 구한다 (항상 정확)."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1


# {1, 3, 4} 동전으로 6원 만들기
print(f"그리디: {min_coins_greedy(6, [1, 3, 4])[0]}개")  # 3개 (4+1+1)
print(f"DP:     {min_coins_dp(6, [1, 3, 4])}개")          # 2개 (3+3)

def erase_overlap_intervals(intervals):
    """
    겹치는 구간을 최소한으로 제거하여 나머지가 겹치지 않게 만든다.
    LeetCode 435. Non-overlapping Intervals
    """
    if not intervals:
        return 0

    # 종료 시간 기준 정렬
    intervals.sort(key=lambda x: x[1])

    # 겹치지 않는 최대 구간 수 구하기 (활동 선택)
    non_overlap = 1
    last_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start >= last_end:
            non_overlap += 1
            last_end = end

    # 제거해야 할 구간 수
    return len(intervals) - non_overlap


# 예제
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2

def find_min_arrows(points):
    """
    모든 풍선을 터뜨리는 최소 화살 수.
    LeetCode 452. Minimum Number of Arrows to Burst Balloons
    """
    if not points:
        return 0

    # 종료 좌표 기준 정렬
    points.sort(key=lambda x: x[1])

    arrows = 1
    arrow_pos = points[0][1]  # 첫 화살은 첫 풍선의 끝 지점에 쏜다

    for start, end in points[1:]:
        if start > arrow_pos:  # 현재 화살로 못 터뜨리면
            arrows += 1
            arrow_pos = end  # 새 화살 발사

    return arrows


# 예제
print(find_min_arrows([[10,16],[2,8],[1,6],[7,12]]))  # 2
print(find_min_arrows([[1,2],[3,4],[5,6],[7,8]]))      # 4

from functools import cmp_to_key

def largest_number(nums):
    """
    숫자 배열을 조합하여 가장 큰 수를 만든다.
    프로그래머스 "가장 큰 수" / LeetCode 179
    """
    # 커스텀 비교: "ab" vs "ba"로 비교
    def compare(x, y):
        if x + y > y + x:
            return -1  # x가 앞에
        elif x + y < y + x:
            return 1   # y가 앞에
        return 0

    # 문자열로 변환 후 커스텀 정렬
    str_nums = [str(n) for n in nums]
    str_nums.sort(key=cmp_to_key(compare))

    # 앞이 모두 0인 경우 처리 (예: [0, 0, 0])
    result = ''.join(str_nums)
    return '0' if result[0] == '0' else result


# 예제
print(largest_number([3, 30, 34, 5, 9]))   # "9534330"
print(largest_number([10, 2]))              # "210"
print(largest_number([0, 0, 0]))            # "0"

def remove_k_digits_for_max(number, k):
    """
    number에서 k개의 숫자를 제거하여 가장 큰 수를 만든다.
    프로그래머스 "큰 수 만들기"

    동작 원리:
    - 스택에 숫자를 하나씩 넣으면서, 현재 숫자가 스택 top보다 크면
      스택에서 작은 숫자를 제거 (제거 횟수 k가 남아있을 때)
    - 이렇게 하면 왼쪽부터 큰 숫자가 오도록 배치됨
    """
    stack = []

    for digit in number:
        # 스택 top보다 현재 숫자가 크면 스택에서 제거 (제거 횟수 남아있을 때)
        while stack and k > 0 and stack[-1] < digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    # 아직 제거 횟수가 남아있으면 뒤에서부터 제거
    if k > 0:
        stack = stack[:-k]

    return ''.join(stack)


# 예제
print(remove_k_digits_for_max("1924", 2))    # "94"
print(remove_k_digits_for_max("1231234", 3)) # "3234"
print(remove_k_digits_for_max("4177252841", 4))  # "775841"

import heapq
from collections import Counter

class HuffmanNode:
    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_tree(text):
    """허프만 트리를 구축한다."""
    # 1단계: 각 문자의 빈도 계산
    freq = Counter(text)

    # 2단계: 최소 힙에 모든 문자를 넣기
    heap = [HuffmanNode(char, f) for char, f in freq.items()]
    heapq.heapify(heap)

    # 3단계: 가장 빈도 낮은 두 노드를 합치기 반복
    while len(heap) > 1:
        left = heapq.heappop(heap)   # 빈도 가장 낮은 노드
        right = heapq.heappop(heap)  # 두 번째로 낮은 노드

        # 합친 노드 생성 (내부 노드는 char=None)
        merged = HuffmanNode(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 if prefix else "0"  # 문자가 1개일 때
        return codes

    get_codes(node.left, prefix + "0", codes)   # 왼쪽: 0
    get_codes(node.right, prefix + "1", codes)  # 오른쪽: 1

    return codes


# 예제 실행
text = "aaaaabbbbbbbbbccccccccccccdddddddddddddeeeeeeeeeeeeeeeefffffffffffffffffffffffffffff"
root = build_huffman_tree(text)
codes = get_codes(root)

freq = Counter(text)
print("문자별 허프만 코드:")
print(f"{'문자':<6}{'빈도':<8}{'코드':<12}{'비트수'}")
print("-" * 36)
for char, code in sorted(codes.items(), key=lambda x: len(x[1])):
    print(f"{char:<6}{freq[char]:<8}{code:<12}{len(code)}")

# 인코딩 길이 비교
original_bits = len(text) * 8  # ASCII 8비트
huffman_bits = sum(freq[c] * len(codes[c]) for c in freq)
print(f"\n원본: {original_bits} bits")
print(f"허프만: {huffman_bits} bits")
print(f"압축률: {huffman_bits/original_bits*100:.1f}%")

def job_scheduling(jobs):
    """
    마감 시한이 있는 작업 스케줄링.
    jobs: [(작업ID, 마감시한, 이익), ...]
    반환: (최대 이익, 스케줄)
    """
    # 1단계: 이익 기준 내림차순 정렬
    sorted_jobs = sorted(jobs, key=lambda x: x[2], reverse=True)

    # 최대 마감 시한 구하기
    max_deadline = max(job[1] for job in jobs)

    # 시간 슬롯 배열 (1-indexed, 0은 미사용)
    slots = [None] * (max_deadline + 1)

    total_profit = 0
    schedule = []

    # 2단계: 이익 큰 작업부터 가능한 슬롯에 배정
    for job_id, deadline, profit in sorted_jobs:
        # 마감 시한부터 역순으로 빈 슬롯 탐색
        for t in range(min(deadline, max_deadline), 0, -1):
            if slots[t] is None:
                slots[t] = job_id
                total_profit += profit
                schedule.append((t, job_id, profit))
                break

    schedule.sort()  # 시간 순 정렬
    return total_profit, schedule


# 예제
jobs = [
    ('A', 2, 100),
    ('B', 1, 19),
    ('C', 2, 27),
    ('D', 1, 25),
    ('E', 3, 15),
]

profit, schedule = job_scheduling(jobs)
print(f"최대 이익: {profit}")
print("스케줄:")
for t, job_id, p in schedule:
    print(f"  시간 {t}: 작업 {job_id} (이익 {p})")

최대 이익: 142
스케줄:
  시간 1: 작업 C (이익 27)
  시간 2: 작업 A (이익 100)
  시간 3: 작업 E (이익 15)