[파이썬] 메모이제이션과 동적 프로그래밍

메모이제이션(memoization) 과 동적 프로그래밍(Dynamic Programming) 

특징

• 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술.
• 재귀처럼 이전으로 돌아가는게 아니라 이미 저장된 값을 불러오는 것

재귀 vs 메모이제이션

대표적으로 피보나치 수열을 생각해보자.

 # 재귀로 구현한 피보나치 수열
def fibo(n):
	if n < 2:
		return n
	else:
		return fibo(n-1) + fibo(n-2)

#메모이제이션을 이용한 피보나치 수열
def fib_memo(n):
	global memo
	if n>=2 and len(memo) <= n:
		memo.append(fib_memo(n-1) + fib_memo(n-2))  #fib(n)의 결과를 memo[n]에 저장
	return memo[n]   #위에서 저장한 값 호출
 
memo = [0,1] #fib(0)과 fib(1)의 결과는 미리 저장

• memo라는 리스트에 계속 원소를 추가해나가면 마지막으로 들어온 원소는 마지막에 저장이 되므로 연산 수가 많지 않음
• 재귀함수를 돌리면 연산 순서가 fib(0)→fib(1)→fib(2)… 으로 반복된 재귀로 인해 연산수가 엄청 늘어남.

어느 부분이 스텍을 활용하는가?

그냥 원소를 추가하기만 하는데 이게 stack인가?

→ 삭제가 없는 것 뿐이다. 스택의 삽입 과정이 반복되는 것이다. 중요한 것은 memo에 가장 마지막으로 추가된 원소가 리스트의 마지막 자리로 들어온다는 것이다.

Dynamic Programming(동적 계획법)

정의

• 그리디 알고리즘과 더불어 최적화 문제를 해결하는 알고리즘.
• 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하는 과정을 반복
• 최종적으로 원래 주어진 입력의 문제를 해결

예시

위의 피보나치 수를 구하는 과정에는 DP가 적용되어 있다.

1. 문제를 부분 문제로 분할

fib(n)은 fib(n-1)과 fib(n-2)의 합이다. 

fib(n-1)은 fib(n-2)와 fib(n-3)의 합이다. 
.
.
.

이를 반복하면서 내려가면 fib(2)는 fib(1)과 fib(0)의 합이라는 것까지 나온다. 

즉, fib(n)을 구하기 위해서는 fib(2)부터 fib(3),fib(4)… fib(n-1)까지 모두 구해야 한다. 

이 상황을 “fib(n)은 fib(n-1),fib(n-2)….fib(2),fib(1),fib(0)의 부분집합이다” 라고 할 수 있다.

1. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다.

fib(2) → fib(3) → fib(4) … 순서로 구한다. 

1. 부분 문제들의 결과는 테이블(위의 예시에서는 memo)에 저장하고 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

반응형

memo[0] = 0
memo[1] = 1
memo[2] = 1
memo[3] = 2
...
memo[n-1] = fib(n-1)
memo[n] = fib(n-1)

이를 코드로 구현하면 다음과 같다.

def fib(n):
	f = [0,1]  #인덱스 0,1은 0,1로 초기화. fib(0)과 fib(1)이다.
	
	for i in range(2,n+1): #2부터 n까지 반복. fib(2)부터 fib(n)을 구하는 것이다.
			f.append(f[n-1] + f[n-2]) #원래는 fib(n-1)함수를 계산했지만 이젠 리스트에서 참조만 해옴
	
	return f[n]  #f 리스트에서 인덱스 n에 해당하는 fib(n)값을 리턴

• 재귀함수 방식과 비교해보면 연산 횟수 자체가 굉장히 차이가 난다. 재귀함수의 경우 계속 함수를 불러오며 연산이 반복되지만 DP 방식은 딱 n번만큼의 연산만 발생한다.