• 재귀 함수에서 구현한 알고리즘의 호출 함수들의 트리
  • 특정 알고리즘은 상당히 많은 중복 호출이 존재

  • 이전에 계산한 값을 메모리에 저장 → 매번 다시 계산하지 않도록 한다.
  • 동적 계획법(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

  • Greedy 알고리즘과 같이 최적화 문제를 해결하는 알고리즘

  • 입력 크기가 작은 부분 문제들을 모두 해결

  • 그 해들을 이용하여 보다 큰 크기의 부분 문제 해결

  • 최종적으로 원래 주어진 입력의 문제 해결


  • 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있다.
  • 최적 부분 구조로 구성된다.

구현

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]를 구하는 과정


def Fibo1(n):
    if n < 2:
        return n
    else:
        return Fibo(n-1) + Fibo(n-2)

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를 구현한 것이 성능 면에서 효율적
  • 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드 발생