[알고리즘] Dynamic Programming : 새꼼달꼼 장사분석(Memoization)

실습설명 
솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요.

 

가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 작성해보세요. Memoization방식으로 작성해보세요.

max_profit_memo는 파라미터 세개를 받습니다.

 

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

- count : 판매할 새꼼달꼼 개수

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

 

 

예를 들어 price_list 가 [0, 100, 400, 800, 900, 1000]이라면,

1. 새꼼달꼼 0개에 0원

2. 새꼼달꼼 1개에 100원

3. 새꼼달꼼 2개에 400원

4. 새꼼달꼼 3개에 800원

5. 새꼼달꼼 4개에 900원

6. 새꼼달꼼 5개에 1000원

 

만약 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?

 

한친구에게 3개를 팔고 다른친구에게 2개를 팔면 800 + 400을 해서 총 1200원의 수익을 낼 수 있겠죠.

 

 

실습

def max_profit_memo(price_list, count, cache):
    # 여기에 코드를 작성하세요
    
    
def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)


# 테스트 코드
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))

힌트1

Memoization 방식으로 문제를풀면 재귀 함수를 사용하는데요. 재귀 함수를 작성할 때 가장 먼저 생각해야 하는 두가지가 무엇인지 기억하시나요?

 

힌트2

재귀함수를 작성할 때에는 base case와 recursive case에 대해 생각해야 합니다.

-recursive case : 현문재가 너무 커서 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

-base case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

 

힌트3

base case는 n이 0이거나 1일 때입니다. 새꼼달꼼 0개 혹은 1개를 팔려고 하면, 부분 문제로 나눌 필요 없이 바로 주어진 가격을 리턴하면 됩니다.

 

힌트4

우리는 Memoization 방식을 사용하기 때문에 cache에 결괏값을 저장해야합니다.

def max_profit_memo(price_list, count, cache):
    # Base Case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격을 바로 리턴한다
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]

힌트5

recursive case에는 두가지 경우가 있습니다.

max_profit_memo(price_list, i, cache)를 호출했다고 가정했을때..

-새꼼달꼼 i개를 팔아서 가능한 최대 수익을 이미 계산한 경우, 즉 cache[i]가 존재 하는 경우.

-새꼼달꼼 i개를 팔아서 가능한 최대 수익을 아직 계산하지 않은 경우, 즉 cache[i]가 존재하지 않는 경우

 

힌트6

def max_profit_memo(price_list, count, cache):
    # Base Case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격을 바로 리턴한다
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]

    # 이미 계산한 값이면 cache에 저장된 값을 리턴한다
    if count in cache:
        return cache[count]

이번에는 조금 복잡한 두번째 경우를 작성하세요.

 

힌트7

새꼼달꼼 2개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까요?

 

1. 2개를 한명에게 팔때의 가격

2. 1개를 팔아서 가능한 최대수익+1개를 팔아서 가능한 최대수익

 

위 두 경우를 비교하면 됩니다. 그렇다면 새꼼달꼼 3개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까요?

 

1. 3개를 한명에게 팔때의 가격

2. 2개를 팔아서 가능한 최대 수익 +1개를 팔아서 가능한 최대 수익

 

위 두 경우를 비교하면 됩니다. 그렇다면 새꼼달꼼 4개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까요?

 

1. 4개를 한명에게 팔떄의 가격

2. 3개를 팔아서 가능한 최대 수익+1개를 팔아서 가능한 최대수익

3. 2개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익

 

위 세 경우를 비교하면 됩니다. 그렇다면 새꼼달꼼 5개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까요?

 

1. 5개를 한명에게 팔떄의 가격

2. 4개를 팔아서 가능한 최대수익 +1개를 팔아서 가능한 최대수익

3. 3개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익

 

위 세경우를 비교하면 됩니다. 그렇다면 새꼼달꼼 6개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까요?

 

1. 6개를 한명에게 팔 떄의 가격

2. 5개를 팔아서 가능한 최대 수익 +1개를 팔아서 가능한 최대 수익

3. 4개를 팔아서 가능한 최대 수익+2개를 팔아서 가능한 최대 수익

4. 3개를 팔아서 가능한 최대수익 +3개를 팔아서 가능한 최대 수익

 

위 네 경우를 비교하면 됩니다. 패턴이 보이시나요?

 

 

 

 

답안

def max_profit_memo(price_list, count, cache):
    # Base Case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격을 바로 리턴한다
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]

    # 이미 계산한 값이면 cache에 저장된 값을 리턴한다
    if count in cache:
        return cache[count]

    # profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
    # 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정
    # 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0

    # count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 profit에 저장
    for i in range(1, count // 2 + 1):
        profit = max(profit, max_profit_memo(price_list, i, cache) 
                 + max_profit_memo(price_list, count - i, cache))

    # 계산된 최대 수익을 cache에 저장
    cache[count] = profit

    return profit


def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)


# 테스트 코드
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))