Memoization & DP (Dynamic Programming) (메모이제이션 및 동적 계획법)

Memoization 설명

• 재귀함수로 구현한 알고리즘은 "엄청난 중복 호출이 존재"한다는 문제점이 존재
• 피보나치 수열의 Call Tree

• 메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
• 동적 계획법의 핵심이 되는 기술
• Memoizaition 방법을 적용한 알고리즘은 아래와 같음

# Memoization
memo = [0,1]

def fibo1(n):
    if n >= 2 and len(memo) <= n:
        memo.append(fibo1(n-1) + fibo1(n-2))
    return memo[n]

# 메모이제이션 활용 후, fibo1(40)도 바로 출력
print(fibo1(40))
print(memo)

###########################################
memo2 = [-1] * 21
memo2[0] = 0
memo2[1] = 1

def fibo2(n):
    if memo2[n] == -1:
        memo2[n] = fibo2(n-1) + fibo2(n-2)

    return memo2[n]

print(fibo2(10))
print(memo2)

DP(Dynamic Programming) 설명

• 동적 계획 (Dynamic Programming) 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 입력 크기가 작은 부분 문제들을 모두 해결한 후, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해나가며, 최종적으로 주어진 문제를 해결하는 알고리즘
• 피보나치 수 DP 적용

# DP 구현 방식 : recursive 방식

memo = [0,1]

def fibo1(n):
    if n >= 2 and len(memo) <= n:
        memo.append(fibo1(n-1) + fibo1(n-2))
    return memo[n]


###############################


# DP 구현 방식 : 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]

• DP의 구현 방식
  • recursive 방식 : fib1()
  • iterative 방식 : fib2()
  • memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 구현한 것이 성능면에서 효율적
  • 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문