✅ AI 채팅 링크: https://gemini.google.com/share/696e65b314d3
Problem definition: To send the letter to my friend, Nate, it costs 140 cents. We have nine postage stamps and each costs, 1, 10, 21, 34, 70, 100, 350, 1225, 1500 cents.
- Step 1: Prompt an AI to “Implement a Dynamic Programming solution to find the minimum count of postage stamps for the 140-cent target”
- Step 2: The AI’s code will likely output the final answer, but it won’t show how it got there. Modify the AI’s code yourself to explicitly print the Dynamic Programming table for every value from target = 1cent up to target = 140cents
- Requirement: Based on your printed table, identify the exact intermediate target value (between 1 and 140) where the DP approach first diverges from the Greedy approach’s choice. Explain why this divergence happens at that specific number.
- Step 3: AI models often write dynamic programming code hardcoded for the specific inputs provided. Test the robustness of the AI’s algorithm by changing the stamp denomination to [5, 4, 1] and the target to 7cents.
- Requirement: Does the AI’s DP code still work correctly? Show the result and your interpretation of it. Also, show what the answer is if you use a greedy algorithm?
- Correction for Step3: Change the stamp denominations to [5, 4, 1] and the target to 8cents.
- Requirement: Does the AI’s code correctly output 2? Show the result
- Step 4: Report the worst-case time and space complexities of the dynamic programming implementation (count basic operations, no recurrence relations needed). Finally, discuss what structural property (e.g., overlapping subproblems, etc) allow dynamic programming to succeed across all test cases where Greedy fails.
Step1
My Prompt
Problem definition: To send the letter to my friend, Nate, it costs 140 cents. We have nine postage stamps and each costs, 1, 10, 21, 34, 70, 100, 350, 1225, 1500 cents.
Implement a Dynamic Programming solution to find the minimum count of postage stamps for the 140-cent target
AI's output code
def min_stamps(stamps, target):
# Initialize DP table with a value larger than any possible solution
# (target + 1 is a safe "infinity" here)
dp = [float('inf')] * (target + 1)
# Base case: 0 cents requires 0 stamps
dp[0] = 0
# Iterate through every value from 1 to target
for i in range(1, target + 1):
for stamp in stamps:
if i >= stamp:
# Update the DP table if using this stamp is better
dp[i] = min(dp[i], dp[i - stamp] + 1)
return dp[target]
# Input Data
stamp_values = [1, 10, 21, 34, 70, 100, 350, 1225, 1500]
target_value = 140
result = min_stamps(stamp_values, target_value)
print(f"Minimum stamps required for {target_value} cents: {result}")Step2
def min_stamps(stamps, target):
# Initialize DP table with a value larger than any possible solution
# (target + 1 is a safe "infinity" here)
dp = [float('inf')] * (target + 1)
# Base case: 0 cents requires 0 stamps
dp[0] = 0
## 미관상 구분 편의를 위한 print문 추가
print(f"{'Target':<8} | {'DP Count':<10}")
print("-" * 20)
# Iterate through every value from 1 to target
for i in range(1, target + 1):
for stamp in stamps:
if i >= stamp:
# Update the DP table if using this stamp is better
dp[i] = min(dp[i], dp[i - stamp] + 1)
print(f"{i:<8} | {dp[i]:<10}") ## 중간 과정 출력 print문 추가
return dp[target]
# Input Data
stamp_values = [1, 10, 21, 34, 70, 100, 350, 1225, 1500]
target_value = 140
result = min_stamps(stamp_values, target_value)
print(f"Minimum stamps required for {target_value} cents: {result}")##으로 시작하는 주석과 코드가 step1의 AI 코드에 내용을 추가한 부분이다. 전체 DP 테이블의 진행 과정을 확인하기 위해 for문 안에 print문을 추가하였다.
DP 접근법과 greedy 방식의 결과값이 가장 처음 달라지는 부분은 target이 30일 때이다.
Greedy 알고리즘은 30센트에서 선택할 수 있는 가장 큰 우표인 21을 우선적으로 선택한다. 하지만 이렇게 되면 남은 9를 채우기 위해 1센트 우표를 9장 사용해야 한다. 따라서 Greedy 알고리즘을 사용하면 21센트 우표 1장과 1센트 우표 9장을 사용하게 되어 총 10장의 우표가 필요하다.
이에 반해 DP 접근법에서는 21센트 우표를 사용하는 방법뿐만 아니라, 10센트 우표를 사용하는 방법 등 하위 문제의 상태를 모두 고려한다. 이때 이미 최적화된 값이 2인 dp[20]의 값을 참조하여, 여기에 10센트 우표 1장만 더 추가하면 30을 만들 수 있다는 것을 알아낸다. 따라서 DP 접근법은 총 3장의 우표가 필요하다.
target이 30센트일 때 두 접근법의 결과가 차이가 발생하는 이유는 문제에서 주어진 우표들간 수학적 배수 관계가 아니기 때문이다. 우표 단위들 간에 완벽한 수학적 배수 관계가 성립하지 않으면, 당장 가장 큰 단위를 선택하였을 때 오히려 남은 부분을 채우기 위해 훨씬 비효율적인 선택을 해야만 하는 상황이 발생한다.
Step3
AI가 작성한 코드가 초기 입력값에만 맞춰진 하드코딩인지, 아니면 다양한 입력값에도 동작하는 범용성을 갖췄는지 테스트하기 위해 입력 데이터를 문제의 수정 요구사항에 맞춰 변경하였다.
def min_stamps(stamps, target):
# Initialize DP table with a value larger than any possible solution
# (target + 1 is a safe "infinity" here)
dp = [float('inf')] * (target + 1)
# Base case: 0 cents requires 0 stamps
dp[0] = 0
## 미관상 구분 편의를 위한 print문 추가
print(f"{'Target':<8} | {'DP Count':<10}")
print("-" * 20)
# Iterate through every value from 1 to target
for i in range(1, target + 1):
for stamp in stamps:
if i >= stamp:
# Update the DP table if using this stamp is better
dp[i] = min(dp[i], dp[i - stamp] + 1)
print(f"{i:<8} | {dp[i]:<10}") ## 중간 과정 출력 print문 추가
return dp[target]
## Input Data 수정
stamp_values = [5, 4, 1]
target_value = 7 ## 실행결과1
## 실행결과2 target_value = 8
result = min_stamps(stamp_values, target_value)
print(f"Minimum stamps required for {target_value} cents: {result}")실행결과1
Target | DP Count
--------------------
1 | 1
2 | 2
3 | 3
4 | 1
5 | 1
6 | 2
7 | 3
Minimum stamps required for 7 cents: 3실행 결과2
Target | DP Count
--------------------
1 | 1
2 | 2
3 | 3
4 | 1
5 | 1
6 | 2
7 | 3
8 | 2
Minimum stamps required for 8 cents: 2실행 결과1과 2를 보면 input data를 수정하여도 AI가 제공해준 코드가 최적해를 정확하게 출력하는 것을 확인할 수 있다. 이를 통해 해당 코드가 특정 값에 종속되지 않고 정상적이고 견고하게 작동함을 증명하였다.
만약 동일한 조건에서 Greedy 알고리즘을 사용하게 된다면 7센트에 대해서는 5센트 1장, 1센트 2장을 사용하여 총 3장이 필요하고, 8센트에 대해서는 5센트 1장, 1센트 3장을 사용하여 총 4장이 필요하다.
Step4
목표 금액인 target을 Y, 우표 종류의 개수를 M이라 하자.
위 코드는 1부터 Y까지 반복하는 바깥 for문과, 각 금액마다 M개의 우표를 모두 확인하는 내부 for문을 가진다. 내부 루프 안에서는 단순 뺄셈, 배열 인덱스 접근, min() 함수를 통한 기본 비교 연산만이 수행된다. 따라서 기본 연산은 정확히 Y x M번 발생하므로, 최악의 경우 시간 복잡도는 O(YM)이다. 공간 복잡도를 살펴보면, 0부터 목표 금액 Y까지의 최소 우표 개수 상태를 저장하기 위해, 크기가 Y+1인 1차원 배열 dp 하나만을 할당하여 사용하므로 공간 복잡도는 O(Y)이다.
마지막으로 Greedy 알고리즘은 실패하지만 DP는 최적해를 구할 수 있는 이유를 알아보자. Greedy 알고리즘은 지역적 최적해에 매몰되어 다른 하위 문제로 이어지는 경로를 완전히 무시해 버린다. 반면, DP는 모든 하위 문제의 가능성을 배재하지 않고 탐색한다. 또한 부분 문제 반복의 특성을 활용하여, 한 번 계산한 하위 문제의 최적값을 메모리에 저장해 두고 재사용한다. 즉, 하위 문제들의 최적해들을 모두 비교하여 큰 문제의 해를 도출하므로, 비효율적인 함정에 빠지지 않고 완벽한 전역 최적해를 보장할 수 있다.
