[알고리즘] Find minimum number of US postage stamps

✅ AI 채팅 링크: https://gemini.google.com/share/821aab7c34f9

Problem definition: To send a letter to my friend, Nate, it costs 140 cents. We have nine postage stamps, each costing: 1500, 1225, 350, 100, 70, 34, 21, 10, 1 cents.
(Note that stamps are sorted in non-increasing order).

• Step 1 (Generate): Prompt an AI with the exact problem definition above and ask it to "implement a greedy algorithm to find the minimum count of postage stamps needed." Document your prompt and the AI's output code.
• Step 2 (Analyze): Run the AI's code. Report the total number of stamps the AI's greedy algorithm suggests, and state the exact combination of stamps it chose. Analyze the time complexity of this greedy implementation.
• Step 3 (Critique & Prove): Show that the AI's greedy implementation does NOT provide the optimal solution.
  • Requirement: State the true optimal solution (which you must find manually or by tracing). Explain the logical flaw in the AI's greedy approach -- why does picking the largest local optimum fail to yield the global optimum for this specific set of stamp denominations?

Step1

My Prompt

Problem definition: To send a letter to my friend, Nate, it costs 140 cents. We have nine postage stamps, each costing: 1500, 1225, 350, 100, 70, 34, 21, 10, 1 cents.
(Note that stamps are sorted in non-increasing order).
implement a greedy algorithm to find the minimum count of postage stamps needed.

AI's output code

def greedy_stamps(target, denominations):
    count = 0
    used_stamps = {}
    
    for stamp in denominations:
        if target >= stamp:
            num_of_stamps = target // stamp
            target -= num_of_stamps * stamp
            count += num_of_stamps
            used_stamps[stamp] = num_of_stamps
            
    return count, used_stamps

# Data
target_value = 140
stamp_values = [1500, 1225, 350, 100, 70, 34, 21, 10, 1]

# Execution
total_count, distribution = greedy_stamps(target_value, stamp_values)

print(f"Minimum stamps needed (Greedy): {total_count}")
print(f"Stamp breakdown: {distribution}")

Step2

실행 결과

Minimum stamps needed (Greedy): 8
Stamp breakdown: {100: 1, 34: 1, 1: 6}

시간 복잡도 분석

위 코드에서 시간 복잡도의 가장 큰 부분을 차지하는 부분은 for문이다. 해당 for문은 denominations 리스트 길이인 n만큼 수행되기 때문에 시간 복잡도는 O(n)이다. 나머지 부분은 모두 O(1)의 시간복잡도를 가진 사칙연산이나 할당연산이므로 전체 시간 복잡도는 O(n)이다.

Step3

진짜 최적해는 70 우표 2장을 사용하는 것이다.

그리디 알고리즘은 현재 단계에서 고를 수 있는 가장 큰 단위를 선택하면, 최종 결과도 최소 개수가 될 것이라는 단편적인 가정을 바탕으로 동작한다. 하지만 위 예에서 주어진 우표 단위들처럼 숫자들 간에 완벽한 배수 관계가 성립하지 않을 때에는 이 논리가 통하지 않는다.

실제로 그리디 알고리즘은 타겟 넘버인 140을 처리할 때, 눈앞의 가장 큰 단위인 100을 우선적으로 선택한다. 이로 인해 남은 40을 채우기 위해 34단위 1장과 1단위 6장을 추가로 사용하게 되어 총 8장을 소모하는 비효율적인 선택을 한다. 즉, 초기에 100이라는 지역적 최적해를 선택해, 70을 2장 선택하여 끝낼 수 있는 전역적 최적해의 경로를 스스로 차단해 버리는 논리적 결함을 가지고 있다.