DP(Dynamic Programming)
def fibonacci_memo(n, memo=None):
"""
메모이제이션을 사용한 피보나치 (하향식 DP)
Args:
n: 피보나치 인덱스
memo: 계산 결과를 저장할 딕셔너리
Returns:
n번째 피보나치 수
"""
memo = {}
memo[0] = 0
memo[1] = 1
def fib_iter(n):
if n in memo:
return memo[n]
else:
a = fib_iter(n - 1)
b = fib_iter(n - 2)
memo[n] = (a + b)
return memo[n]
fib_iter(n)
return memo[n]
# 테스트 케이스
if __name__ == "__main__":
# 테스트 케이스 1
print("=== 피보나치 수열 (메모이제이션) ===")
for i in range(11):
result = fibonacci_memo(i)
print(f"fib({i}) = {result}")
print()
# 테스트 케이스 2: 큰 수도 빠르게 계산
print("=== 큰 수 계산 ===")
n = 50
result = fibonacci_memo(n)
print(f"fib({n}) = {result}")
print()
# 비교: Week1의 재귀 방식은 fib(50)을 계산하기 어려움
print("참고: 일반 재귀는 fib(40)도 몇 초 걸리지만")
print("메모이제이션은 fib(100)도 순식간에 계산!")DP는 기본적으로 점화식이라는 거를 생각하게 한다.
그러면 DP(n) = DP(n-1) + DP(n-2)로 표현된다.
이런식으로 표현할 때 쭈욱 적게 되면
3 = 2 + 1
4 = 3 + 2
5 = 4 + 3 …
이런 식으로 이전 연산 값이 다음 연산에 쓰이는 구조가 나오게 된다.
그러면 우리가 생각해야 할 부분은 왜 내가 이거를 또 해야하는거지? 라는 생각이다.
재귀가 같은 일을 반복할 때
재귀는 말하듯이 짜는 상황인데 한 말 또 해야하는 상황이다. 그러면 이때 DP가 개발자한테 말을 거는 것이다.
이거 저번에 했잖아
그러면 개발자는 그 저번에 한 결과물을 받고 아 맞네 하는 그런 흐름을 가져간다.
그 중에서도 보통 DP가 굉장히 유의미한 상황은 재귀가 반복되는 일을 계속 하는데 그대로 두면 분명하게 문제가되는 상황이다.
피보나치 수열
피보나치 수열은 n을 구하기 위해선 n-1과 n-2의 값을 더해야 한다.
그러면 1번 재귀 때 n-1, n-2 그리고 다음 재귀 때 n-1 에서 n-2와 n-3 … 등으로 약 2개씩 계속하여 늘어나게된다.
이러한 경우가 그대로 두면 문제가 되는 경우이다.
이러한 경우는?
위에서 구현한 것과 같이 memo 기능을 추가하여 만약 이전에 연산했다면? 연산을 진행하지 않고 배열에 있는 값을 반환해준다.
하지만, 만약 연산한 적이 없다면 원래 하던대로 재귀를 하고 거기서 응답 받은 값을 배열에 집어 넣으면 된다.
모든 재귀가 아닌
- 중복 부분 문제 : 같은 하위 문제가 여러 번 등장
- 최적 부분 문제 : 큰 문제의 답이 작은 문제의 답으로 조립
이러한 경우 DP를 사용하게 된다.
두가지 방법
- 탑 다운 : 위의 코드와 같다. 재귀를 호출하고 내려가며 배열을 채워 추후 불필요한 연산을 없앰
- 바텀 업 : 0 혹은 1과 같이 밑바닥 값부터 시작하여 계속해서 채워나간 후 목표 값을 리턴
def climb_stairs(n):
dp = {}
dp[0] = 0
dp[1] = 1
dp[2] = 2
# dp[0] = 0
# dp[1] = 1, 1칸을 오르는 경우의 수는 1
# dp[2] = 2, 1칸 2번, 2칸 한번에
# dp[3] = 3, 1칸 3번, 1칸 오르고 2칸, 2칸 오르고 1칸
# dp[4] = , dp[3] + 1 / 3칸을 어찌됐건 오르고, 1칸 더 오르기, dp[2] + 2 (2칸을 오르는 방법은 2가지)
for idx in range(3, n+1):
dp[idx] = dp[idx -2] + dp[idx-1]
return dp[n]이 방식은 다음 문제 였던 계단 문제를 바텀 업을 통하여 구한 방식이다.
계단을 오르는 방법의 수를 구하는 것이고 1칸 or 2칸 올라가고 목표 값에 다가가기 위해선 어디와 어디를 더해야 하는 지를 확인하고 아래에서부터 목표값인 위로 올렸다.
