![[Algorithm] 메모이제이션과 동적계획법(Memoization and DP)](/_next/image?url=https%3A%2F%2Fblog.huns.site%2Fimgs%2Fthumbnails%2Fblog%2Fposts%2Fcomputer-science%2Falgorithm.png&w=1200&q=75)
TOC
Call Tree
- 재귀 함수에서 구현한 알고리즘의 호출 함수들의 트리
- 특정 알고리즘은 상당히 많은 중복 호출이 존재
메모이제이션(Memoization)
- 이전에 계산한 값을 메모리에 저장 → 매번 다시 계산하지 않도록 한다.
- 동적 계획법(DP)의 핵심이 되는 기술
알고리즘
# memo를 위한 배열을 할당하고, 모두 0으로 초기화
def fibo1(n):
global memo
if n >= 2 and len(memo) <= n: # memo의 길이보다 n이 크거나 같으면, 값을 만들어야 함.
memo.append(fibo1(n-1) + fibo1(n-2))
return memo[n] # memo에 n에 해당하는 값이 있으니까 계산없이 바로 반환
# memo[0]을 0으로 memo[1]는 1로 초기화
memo = [0, 1]
만약 스택처럼 메모리를 미리 선점하여 운용하고 싶다면 memo를 아래처럼 정의하면 된다.
def fibo1(n):
global memo
if n >= 2 and len(memo) <= n: # memo의 길이보다 n이 크거나 같으면, 값을 만들어야 함.
memo.append(fibo1(n-1) + fibo1(n-2))
return memo[n] # memo에 n에 해당하는 값이 있으니까 계산없이 바로 반환
memo = [0]*n
memo[1] = 1
동적 계획법(DP; Dynamic Programming)
-
Greedy 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
-
입력 크기가 작은 부분 문제들을 모두 해결
-
그 해들을 이용하여 보다 큰 크기의 부분 문제 해결
-
최종적으로 원래 주어진 입력의 문제 해결
피보나치 수 DP 적용
- 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있다.
- 최적 부분 구조로 구성된다.
구현
N = 10
Fibo = [0]*(N+1)
Fibo[0] = 0
Fibo[1] = 1
for i in range(N+1):
Fibo[i] = Fibo[i-1] + Fibo[i-2]
print(Fibo)
문제를 부분 문제로 분할
Fibo(n) = Fibo(n-1) + Fibo(n-2)
Fibo(n-1) = Fibo(n-2) + Fibo(n-3)
...
Fibo(2) = Fibo(1) + Fibo(0)
부분 문제로 나누었다면 가장 작은 부분 문제부터 해 구하기
위에서는 Fibo[0]과 Fibo[1]을 각각 0과 1로 초기화한 것.
결과를 테이블에 저장, 테이블에 저장된 부분 문제의 해를 이용해 상위 문제의 해를 구하기
위에서는 Fibo[i-1]과 Fibo[i-2]를 통해 Fibo[i]를 구하는 과정
DP의 구현 방식
recursive 방식
def Fibo1(n):
if n < 2:
return n
else:
return Fibo(n-1) + Fibo(n-2)
iterative 방식
def Fibo2(n):
f = [0, 1]
for i in range(2, n+1):
f.append(f[i-1] + f[i-2])
return f[n]
특징
- Memoization을 재귀적 구조(Fibo1(n))에 사용하는 것보다 반복적 구조(Fibo2(n))로 DP를 구현한 것이 성능 면에서 효율적
- 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드 발생
