Dynamic Programming 마지막 시간입니다.
저번 시간에는 Dynamic Programming의 두 번째 풀이법 Tabulation을 배우고 Memoization과 비교했을 때 장단점을 알아봤습니다.
이번 시간에는 Dynamic Programming의 새로운 예제를 풀어보겠습니다. 두 가지 풀이법을 각각 사용해서 말이죠.
🥮 쬬꼬빠이 매출 분석
타키탸키는 최근 SNS에 화제가 되고 있는 쬬꼬빠이를 팔아 장사를 하려 합니다. 장사 시작 전, 매출을 올리기 위해 최대 수익을 분석하기 시작했는데요.
최대 수익을 리턴해주는 함수 max_profit을 가정해봅시다. max_profit은 파라미터로 개수별 가격이 정리된 리스트 price_list와 판매할 쬬꼬빠이 개수 count를 받습니다.
예시를 한 번 볼까요? 만약 price_list가 [200, 500, 900, 1000, 1100]이라면,
- 쬬꼬빠이 1개: 200원
- 쬬꼬빠이 2개: 500원
- 쬬꼬빠이 3개: 900원
- 쬬꼬빠이 4개: 1000원
- 쬬꼬빠이 5개: 1100원
개당 이런 식으로 가격을 정했습니다. 그렇다면 타키탸키가 오늘 쬬꼬빠이 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?
명심하세요. 한 명에게 5개를 모두 팔아 1100원을 버는 것보다 한 친구에게 3개를 팔고 다른 친구에게 2개를 팔아 총 1400원을 버는 것이 더 이득일 수 있습니다.
❗ 생각해보기
이 문제를 Dynamic Programming 방식으로 풀기 위해서는 먼저 조건에 부합하는지 따져봐야 합니다. 두 가지 조건이 있었죠? 하나는 '문제가 최적 부분 구조를 가지고 있는가'였고 다른 하나는 '중복되는 부분 문제를 가지고 있는가'였습니다.
첫 번째 조건부터 볼까요? 쬬꼬빠이 5개를 팔 수 있는 방식은 여러 가지입니다. 한 친구에게 5개를 모두 팔 수도 있지만 두 친구에게 각각 4개, 1개를 팔거나 3개, 2개를 팔 수도 있습니다. 이때, 최대 수익을 구하려면 다음과 같습니다.
- 5개를 한 명에게 팔 때 가격
- 4개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
- 3개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익
이 중에서 가장 큰 값을 가지는 항목이 최대 수익이 됩니다. 결국 5개를 팔아서 가능한 최대 수익을 찾으려면 4개를 팔았을 때 가능한 최대 수익, 3개, 2개, 1개를 팔았을 때 가능한 최대 수익을 모두 알아야 합니다.
따라서, 부분 문제의 답을 이용해서 기존 문제의 답을 구할 수 있기 때문에 최적 부분 구조를 가지고 있다고 할 수 있습니다.
다만, 두 부분 문제의 답을 더한 것이 기존 문제의 답이 되는 피보나치 수열과는 다르게 이 문제의 경우 단순히 합을 통해 기존 문제를 해결할 수 없기 때문에 조금 더 깊이 생각해 봐야 합니다.
이번에는 두 번째 조건을 봅시다. 앞서, 5개를 팔아서 가능한 최대 수익을 찾기 위해서는 4개, 3개, 2개, 1개를 팔아서 가능한 최대 수익을 모두 알아야 된다고 했는데요. 이 과정에는 같은 부분 문제가 여러 번 등장합니다. 따라서, 중복되는 부분 문제를 가지고 있다고 할 수 있죠.
두 가지 조건을 모두 만족하기 때문에 이 문제는 Dynamic Programming으로 풀이가 가능합니다😊😊😊
🥮 쬬꼬빠이 Memoization
memo_max_profit은 max_profit 함수를 Memoization 방식으로 구현한 함수입니다. 이 함수는 파라미터 세 개가 필요한데요.
- price_list: 개수별 가격이 정리되어 있는 리스트
- count: 판매할 쬬꼬빠이 개수
- cache: 개수별 최대 수익이 저장되어 있는 사전
Memoization 방식은 재귀 함수를 통해 코드를 구현한다 했죠? 재귀 함수를 작성할 때 가장 먼저 생각해야 할 것이 무엇인가요? 네, 맞습니다. base case와 recursive case를 구해야죠.
이 문제의 base case를 구해봅시다. 쬬꼬빠이를 하나도 팔지 않거나 1개를 팔 때는 부분 문제로 나눌 필요 없이 바로 주어진 가격을 반환하면 됩니다. 개수별 최대 수익을 구하는 문제이기 때문에 0개 혹은 1개라면 그 하나의 값만 제시하면 되니까요.
Memoization 방식은 반복되는 연산 결과를 cache라는 저장 공간에 넣어둔다고 했었죠? 이 공간부터 만들어 봅시다.
def max_profit(price_list, count):
max_profit_cache = {}
return max_profit_memo(price_list, count, max_profit_cache)이제 cache에 결괏값을 저장해봅시다.
def memo_max_profit(price_list, count, cache):
if count < 2:
cache[count] = price_list[count]
return price_list[count]count가 2보다 작을 때 즉, 쬬꼬빠이를 0개 혹은 1개 팔 때, 파라미터로 입력된 price_list에서 count의 인덱스에 해당하는 값은 cache 사전의 count 키값이 됩니다. 그리고 그 값을 반환하면 되죠.
이제 recursive_case를 볼까요? 이 문제에는 두 가지 recursive case가 있습니다.
- 쬬꼬빠이 count개를 팔아서 가능한 최대 수익을 이미 계산한 경우. 즉, cache[count]가 존재하는 경우
- 쬬꼬빠이 count개를 팔아서 가능한 최대 수익을 아직 계산하지 않은 경우. 즉, cache[count]가 존재하지 않는 경우
첫 번째 case가 더 간단하므로 먼저 작성해봅시다.
if count in cache:
return cache[count]그럼 두 번째 case는 어떻게 작성하면 좋을까요? 이제부터 좀 복잡해지므로 가능한 경우를 하나씩 나누어봅시다.
쬬꼬빠이 2개를 팔아서 가능한 최대 수익은 다음과 같습니다.
- 2개를 한 명에게 팔 때의 가격
- 1개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
두 경우를 비교하여 더 큰 값이 최대 수익이 됩니다. 쬬꼬빠이 3개를 팔 때는 어떨까요?
- 3개를 한 명에게 팔 때의 가격
- 2개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
4개부터는 간단히 봅시다.
4개: (4개 / 3개 + 1개 / 2개 + 2개)
5개: (5개 / 4개 + 1개 / 3개 + 2개)
6개: (6개 / 5개 + 1개 / 4개 + 2개 / 3개 + 3개)
우선, 팔려고 하는 총 개수에 대한 가격이 price_list에 없는 경우와 있는 경우를 나눠서 생각해야 합니다. 그리고 count개를 팔아서 가능한 최대 수익을 저장하기 위해 max_price 변수가 필요합니다.
max_price는 팔려고 하는 총 개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정하고 없으면 0으로 설정하도록 합시다.
if count < len(price_list):
max_price = price_list[count]
else:
max_price = 0price_list에는 개수별 가격이 저장되어 있기 때문에 count의 수를 확인하려면 price_list의 길이보다 count의 값이 작아야 합니다. 값이 클 때는 필요 없는 값이므로 0으로 설정해두는 거죠.
이제 해야할 일은 count개를 팔 수 있는 조합들을 비교해서 가능한 최대 수익을 max_price에 저장해야 합니다. 이때, 재귀 함수를 사용해야 한다는 것을 잊지 마세요.
for n in range(1, count // 2 + 1):
max_price = max(max_price, memo_max_profit(price_list, n, cache)
+ memo_max_price(price_list, count - n, cache))여기서 마지막 인덱스를 'count // 2 + 1'로 잡은 이유는 중복되는 경우를 제외하기 위함입니다. 예컨대, (2, 3)과 (3, 2)는 같은 case이기 때문에 한 경우는 제외해야 하죠.
count가 3일 때, 2라는 수는 어떻게 표현할 수 있을까요? 두 수의 합이 최종적으로 판매할 개수인 5이기 때문에 총 개수 5에서 3을 빼면 됩니다. 따라서, 'count - n'을 파라미터로 추가한 거죠.
미리 설정해둔 max_price와 재귀 함수를 통해 구한 값들을 비교하여 더 큰 값을 max_price에 넣어 갱신합니다. 그리고 이 값을 cache 사전의 count 키값으로 설정해야 합니다. 마지막으로 max_price를 리턴하면 끝입니다.
cache[count] = max_price
return max_price이제 전체 코드와 예시를 봅시다.
def memo_max_profit(price_list, count, cache):
if count < 2:
cache[count] = price_list[count]
return price_list[count]
if count in cache:
return cache[count]
if count < len(price_list):
max_price = price_list[count]
else:
max_price = 0
for n in range(1, count // 2 + 1):
max_price = max(max_price, memo_max_profit(price_list, n, cache)
+ memo_max_profit(price_list, count - n, cache))
cache[count] = max_price
return max_price
def max_profit(price_list, count):
max_profit_cache = {}
return memo_max_profit(price_list, count, max_profit_cache)print(max_profit([0, 200, 500, 900, 1000, 1100], 5))1400🥮 쬬꼬빠이 Tabulation
tab_max_profit은 max_profit 함수를 Tabulation 방식으로 구현한 함수입니다. 이 함수는 파라미터 두 개가 필요합니다.
- price_list: 개수별 가격이 정리되어 있는 리스트
- count: 판매할 쬬꼬빠이 개수
Tabulation은 테이블을 만들어 기존 문제를 풀기 위한 부분 문제들의 결과를 저장해 두었죠? 따라서, 계산된 최대 수익을 저장해둘 테이블이 필요합니다. 코드 상으로는 리스트가 테이블이 됩니다.
이때, 쬬꼬빠이 0개로 가능한 최대 수익은 0원이므로 profit_table의 첫 요소를 0으로 둡시다.
profit_table = [0]이제 우리가 해야할 일은 profit_table을 인덱스 1부터 인덱스 count까지 채워나간 후에 인덱스 count의 항목을 리턴하는 것입니다.
이때 사례들은 Memoization과 동일합니다. 반복문의 기준도 마찬가지구요.
1개부터 count개까지 계산하기 위한 반복문을 만들어 봅시다.
for i in range(1, count + 1):이제부터는 Memoization의 코드와 유사합니다. 먼저, 인덱스 i가 price_list 길이보다 작은 값일 때는 price_list의 i 인덱스에 해당하는 값을 max_price의 값으로 설정하면 되고 아닌 경우에는 0으로 둡니다.
if i < len(price_list):
max_price = price_list[i]
else:
max_price = 0이제 count개를 팔 수 있는 조합들을 비교하고 큰 값을 max_price에 저장해줘야 하는데요. 이 또한 Memoization 코드와 유사합니다.
이때, Memoization과 다른 점은 사전형 cache와 다르게 리스트 profit_table에 값을 넣어줘야 한다는 것과 재귀 함수가 아닌 반복문으로 해당 과정을 진행해야 한다는 것이죠.
for j in range(1, i // 2 + 1):
max_price = max(max_price, profit_table[j] + profit_table[i - j])
profit_table.append(max_price)이제 전체 코드와 예시를 봅시다.
def tab_max_profit(price_list, count):
profit_table = [0]
for i in range(1, count + 1):
if i < len(price_list):
max_price = price_list[n]
else:
max_price = 0
for j in range(1, i // 2 + 1):
max_price = max(max_price, profit_table[j] + profit_table[i - j])
profit_table.append(max_price)
return profit_table[count]print(max_profit([0, 200, 500, 900, 1000, 1100], 5))1400이로써 Dynamic Programming 챕터가 마무리 되었습니다. 많이 복잡하셨나요? 개인적으로 분기가 명확히 나누어지고 조건도 명확하게 설정되어 있어 다른 알고리즘 프로그래밍보다는 설계가 용이했던 것 같습니다.
이제 마지막 산만 넘으면 됩니다. 다음 시간에는 마지막 알고리즘 패러다임 Greedy Algorithm을 함께 배워봅시다.
* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.