동적 계획법 Dynamic Programming이란 한 번 계산한 결과를 재활용하는 방식을 말한다.
▪️ 조건
최적 부분 구조가 있고, 중복되는 부분 문제들이 있다면 Dynamic Programming으로 문제 해결 가능하다.
① 최적 부분 구조 Optimal Substructure
- 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다.
- 즉, 기존 문제를 부분 문제로 나눠서 풀 수 있다.
② 중복되는 부분 문제 Overlapping Subproblems
▪️ 구현 방법
2가지 방법 모두 중복되는 부분 문제의 비효율을 해결해준다.
① Memoization
- 중복되는 계산은 한 번만 계산한 후 메모하는 방식 (하향식 접근)
- 저장해 놓는 공간 :
캐시 Cache - 재귀 함수 사용 (스택에 과부하 발생 시 에러 발생)
- 필요없는 계산을 안 해도 된다는 장점이 있다.
# Memoization
# fib(6) ~> fib(1)
def fib_memo(n, cache):
# base case
if n < 3 :
return 1
# recursive case
if n in cache :
return cache[n]
else :
cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
return cache[n]
def fib(n):
# n번째 피보나치 수를 담는 사전
fib_cache = {}
return fib_memo(n, fib_cache)② Tabulation
- Table 방식으로 구현하는 것 (상향식 접근)
- 반복문 사용 (모든 값을 계산한다)
# Tabulation
# fib(1) ~> fib(6)
def fib_tab(n):
fib_table = [0, 1, 1]
for i in range(3, n+1) :
fib_table.append(fib_table[i-2] + fib_table[i-1])
return fib_table[n]이 결과 시간 복잡도 O(n), 공간 복잡도 O(n)이 된다.
다만 fib(5)를 구하기 위해서는 fib(4)와 fib(3)만 알면 되므로, 최근 값을 저장하는 변수를 이용하여 좀 더 효율적으로 바꿀 수 있다.
- 현재 값 : current
- 이전 값 : previous
이렇게 된다면 사용하는 메모리는 고정되어 있기 때문에 공간 복잡도 O(1)이 된다.
# Tabulation + 공간 최적화
def fib_optimized(n):
current = 1
previous = 0
for _ in range(1, n) :
current, previous = current + previous, current
return current🖍️ Dynamic Programming으로 문제를 풀 때,
모든 계산값을 저장할 필요가 없다면 공간 사용을 최적화하는 것을 고려해보자.
알고리즘 예제
- 새콤달콤 장사의 최대 수익
- N을 사용하여 number를 만들기 위한 최소 연산 횟수
➲ 새콤달콤 장사의 최대 수익
문제 : 가능한 최대 수익을 리턴시켜 주는 함수 max_profit을 작성해 보세요.
max_profit은 파라미터로 개수별 가격이 정리되어 있는 리스트 price_list와 판매할 새꼼달꼼 개수 count를 받습니다.
예를 들어 price_list가 [100, 400, 800, 900, 1000]이라면,
1개에 100원, 2개에 400원, 3개에 800원, 4개에 900원, 5개에 1000원
이렇게 가격이 책정된 건데요.
만약 오늘 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?
한 친구에게 3개 팔고 다른 친구에게 2개를 팔면, 800 + 400을 해서 총 1200원의 수익을 낼 수 있겠죠.최적 부분 구조
5개를 팔아서 가능한 최대 수익을 찾기 위해서는 4개를 팔아서 가능한 최대 수익, 3개를 팔아서 가능한 최대 수익, 2개를 팔아서 가능한 최대 수익, 1개를 팔아서 가능한 최대 수익을 모두 알아야 하는 거죠.
부분 문제의 답을 이용해서 기존 문제의 답을 구할 수 있기 때문에 이 문제에는 최적 부분 구조가 있습니다.
이 문제에서는 부분 문제들의 답을 단순히 더하는 것이 아니기 때문에, 최적 부분 구조를 찾기 위해서 조금 더 고민이 필요합니다.
중복되는 부분 문제
5개를 팔아서 가능한 최대 수익을 찾기 위해서는 4개를 팔아서 가능한 최대 수익, 3개를 팔아서 가능한 최대 수익, 2개를 팔아서 가능한 최대 수익, 1개를 팔아서 가능한 최대 수익을 모두 알아야 합니다. 즉, 기존 문제를 풀기 위해서 부분 문제들을 풀어야 한다는 거죠.
# Memoization 방식
def max_profit_memo(price_list, count, cache):
# 개수별 가격이 정리되어 있는 리스트, 판매할 새꼼달꼼 개수, 개수별 최대 수익이 저장되어 있는 사전
# base case
if count < 2 :
cache[count] = price_list[count]
return cache[count]
# recursivecase
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)# Tabulation 방식
def max_profit(price_list, count):
# 개수별로 가능한 최대 수익을 저장하는 리스트
# 새꼼달꼼 0개면 0원
profit_table = [0]
# 개수 1부터 count까지 계산하기 위해 반복문
for i in range(1, count + 1):
# profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
# 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정
# 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정
if i < len(price_list):
profit = price_list[i]
else:
profit = 0
# count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 찾는다
for j in range(1, i // 2 + 1):
profit = max(profit, profit_table[j] + profit_table[i - j])
profit_table.append(profit)
return profit_table[count]➲ N을 사용하여 number를 만들기 위한 최소 연산 횟수
def solution(N, number):
# 8개의 집합을 생성, 각 집합은 연산 횟수(1회부터 8회까지)별 가능한 결과를 저장
s = [set() for x in range(8)]
# 각 집합에는 N, NN, NNN, ...과 같은 연속된 숫자 조합을 추가
for i, x in enumerate(s, start=1):
x.add(int(str(N) * i))
for i in range(8):
for j in range(i): # 현재 집합 s[i]를 계산하기 위해 이전 단계의 결과인 s[j]와 s[i-j-1]을 사용
for l in s[j]:
for r in s[i - j - 1]:
# 가능한 모든 연산을 수행하여 결과 집합 s[i]에 추가
s[i].add(l + r) # 덧셈
s[i].add(l - r) # 뺄셈
s[i].add(l * r) # 곱셈
if r != 0:
s[i].add(l // r) # 나눗셈 (0으로 나누지 않도록 조건 추가)
# 목표 숫자 number를 현재 집합 s[i]에서 찾으면, i + 1을 반환 (연산 횟수)
if number in s[i]:
return i + 1
# 목표 숫자를 만들 수 없는 경우 -1 반환
return -1코드잇 - 알고리즘 패러다임
planning design development with data