[파이썬] 알고리즘 패러다임 : Dynamic Programming 연습문제

2023.02.28 코드잇 학습내용

 

🔎 Dynamic Programming 연습문제 

가지고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익 구하기

price_list : 개수별 가격이 정리되어 있는 리스트

count : 판매할 새꼼달꼼 개수

cache : 개수별 최대 수익이 저장되어 있는 사전

 

📖 memoization으로 문제 풀기

① base case : 0개 팔았을 때 혹은 1개 팔았을 때에는 price_list의 가격 그대로 출력

② recursive case : 최대 수익 구하기

 

1개 팔았을 때 수익 : 100
2개 팔았을 때 나올 수 있는 수익 : (1개, 1개) 팔았을 때 혹은 (2개, 0개) 팔았을 때
3개 팔았을 때 나올 수 있는 수익 : (1개, 2개) 팔았을 때 혹은 (3개, 0개) 팔았을 때
4개 팔았을 때 나올 수 있는 수익 : (1개, 3개) 팔았을 때 혹은 (2개, 2개) 팔았을 때 혹은 (0개, 4개) 팔았을 때
5개 팔았을 때 나올 수 있는 수익 : (1개, 4개) 팔았을 때 혹은 (2개, 3개) 팔았을 때 혹은 (0개, 5개) 팔았을 때
...
n개 팔았을 때 나올 수 있는 수익 : (1개, n-1개) & (2개, n-2개) & (3개, n-3개) & ( n // 2개, n - n // 2개) & (0개, n개)
for i in range(1, n // 2 + 1):
    profit = max(max_profit_memo(price_list, i, cache) + max_profit_memo(price_list, n - i, cahce)
   #여기서 0개, n개 판매했을 때 나오는 수익은 확인 안했음

여기서 0개, n개 판매가 가능한 경우는 n이 price_list의 리스트 개수보다 작거나 같은 경우에만 가능
if n < len(price_list):
    profit = price_list[n]
else:
    profit = 0

위의 경우의 수를 모두 확인하여 가장 큰 값을 최대 수익으로 저장
profit = max(profit, max_profit_memo(price_list, i, cache) + max_profit_memo(price_list, n - i, cahce))

 

📖 Tabulation으로 문제 풀기

반복문 사용하여 리스트 채우기

 

▼▼▼ 내가 작성한 코드 ▼▼▼

차이점 : for 반복문을 사용하지 않고 바로 max값을 계산해서 리스트에 저장

답은 맞지만 for 반복문을 사용하지 않으면 틀릴 수도 있으므로 for 반복문을 사용해서 1, i -1부터 2//n, 1 - 2//n까지의 경우의 수 중 가장 큰 값을 저장하도록 해야함