연습 문제

탐욕 문제는 "무엇을 기준으로 줄 세울까"를 찾는 순간 대부분 풀립니다. 아래 네 문제는 각각 다른 탐욕 기준을 연습하도록 만든 것입니다. 풀이를 보기 전에 기준을 먼저 정하고, 그 기준이 왜 옳은지 한 문장으로 설명해 보세요.

문제 1. 점검 시각 정하기

공장의 센서마다 값을 확인해야 하는 시간 창 [l, r](양 끝 포함)이 있습니다. 점검원은 정한 시각에 한 번 순회하며, 그 시각을 포함하는 창의 센서를 모두 확인합니다. 모든 센서를 확인하는 데 필요한 최소 점검 횟수와 그 시각들을 구하세요.

접근: 창을 끝 시각순으로 정렬합니다. 아직 확인되지 않은 창 중 가장 일찍 끝나는 창은 어차피 그 끝 시각 이전에 점검해야 하므로, 가능한 한 늦은 시각인 r에 점검을 두는 것이 뒤의 창을 가장 많이 덮습니다. 교환 논법으로 보면, 최적해의 첫 점검 시각을 r로 옮겨도 덮는 창이 줄지 않습니다.

def min_check_times(windows):
    times = []
    for l, r in sorted(windows, key=lambda w: w[1]):
        if not times or times[-1] < l:  # 마지막 점검이 이 창보다 앞이면
            times.append(r)
    return times


print(min_check_times([(1, 4), (2, 6), (5, 8), (7, 9), (10, 12)]))  # [4, 8, 12]

문제 2. 향신료 싣기(분할 가능 배낭)

수레에 최대 W kg을 실을 수 있고, 향신료마다 전체 가치와 무게가 있습니다. 향신료는 원하는 만큼 덜어서 실을 수 있습니다. 실을 수 있는 최대 가치를 구하세요.

접근: kg당 가치가 높은 향신료부터 담습니다. 남은 용량보다 무거우면 남은 만큼만 덜어 담고 끝냅니다. 비싼 것을 조금 덜고 그 자리에 싼 것을 담는 해는 항상 손해이므로 이 기준이 최적입니다. 정확한 값이 필요하면 fractions.Fraction을 쓰고, 정렬은 나눗셈 대신 곱셈 비교로 바꿀 수도 있습니다.

def max_cart_value(items, capacity):
    """items: (가치, 무게) 목록."""
    total = 0.0
    for value, weight in sorted(items, key=lambda it: it[0] / it[1], reverse=True):
        if capacity <= 0:
            break
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
    return total


print(max_cart_value([(120, 3), (100, 5), (60, 4)], 10))  # 250.0

같은 물건을 쪼갤 수 없다면(0/1 배낭) 이 방법은 틀립니다. 예를 들어 (60, 10), (100, 20), (120, 30)에 용량 50이면 가치 비율 순 탐욕은 160을 얻지만 최적은 220입니다.

문제 3. 마감 안에 끝내는 작업 수

작업마다 걸리는 시간과 마감 시각이 있고, 한 번에 하나씩 쉬지 않고 처리합니다. 시각 0에 시작해 마감 안에 끝나는 작업의 수를 최대로 하세요(마감을 넘길 작업은 아예 하지 않습니다).

접근: 마감이 이른 순서로 작업을 일단 받아들이고, 누적 시간이 마감을 넘으면 지금까지 받아들인 것 중 가장 오래 걸리는 작업을 버립니다. 버릴 때 가장 긴 작업을 고르면 남은 작업 수는 같으면서 누적 시간이 가장 많이 줄어 이후에 유리합니다. 최대 힙이 필요하므로 Python에서는 음수를 넣습니다.

import heapq


def max_on_time(tasks):
    """tasks: (걸리는 시간, 마감) 목록."""
    heap, time = [], 0
    for duration, deadline in sorted(tasks, key=lambda t: t[1]):
        heapq.heappush(heap, -duration)
        time += duration
        if time > deadline:
            time += heapq.heappop(heap)  # 음수이므로 가장 긴 작업 시간을 뺀다
    return len(heap)


print(max_on_time([(3, 4), (2, 5), (4, 7), (1, 8), (3, 9)]))  # 4

문제 4. 파일 합치기 최소 비용

크기가 다른 파일 n개를 하나로 합치려 합니다. 두 파일을 합칠 때마다 두 크기의 합만큼 비용이 듭니다. 전체 최소 비용을 구하세요.

접근: 각 파일의 크기는 합쳐지는 횟수(트리의 깊이)만큼 비용에 더해지므로, 이 문제는 허프만 부호화와 같은 구조입니다. 매번 가장 작은 두 파일을 합칩니다.

import heapq


def min_merge_cost(sizes):
    heap = list(sizes)
    heapq.heapify(heap)
    cost = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        cost += a + b
        heapq.heappush(heap, a + b)
    return cost


print(min_merge_cost([4, 3, 2, 6]))  # 29

순서대로(4+3, 7+2, 9+6) 합치면 7 + 9 + 15 = 31이 드는데, 탐욕은 2+3, 4+5, 6+9로 5 + 9 + 15 = 29를 얻습니다.

스스로 확인하기

• 각 풀이를 완전 탐색과 비교하는 작은 무작위 시험을 만들어 보세요. 입력 크기 6~8이면 순식간에 끝납니다.
• 문제 1에서 창이 반열린 구간이면 비교식이 어떻게 바뀌는지 생각해 보세요.
• 문제 3에서 "가장 긴 작업 버리기" 대신 "방금 넣은 작업 버리기"를 하면 반례가 생기는지 찾아보세요.

정리

• 점검 시각: 끝 시각순 정렬, 덮이지 않은 창의 끝에 점을 둡니다.
• 분할 가능 배낭: 무게당 가치순, 마지막 하나만 덜어 담습니다.
• 마감 작업: 마감순으로 넣고 넘치면 힙에서 가장 긴 작업을 버립니다.
• 파일 합치기: 허프만과 같이 가장 작은 두 개를 계속 합칩니다.