[Dynamic Programming] - Memoization

https://galid1.tistory.com/507

 

 

동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 점에서는 분할 정복과 맥락을 같이 하는데 동적 프로그래밍의 의의는 작은 문제들 사이에 중복이 발생하는 경우에 효과적이라는 것입니다.

 

즉 작은 문제들이 반복되는 경우 이 작은 문제들은 한 번만 풀고 그 뒤로 메모에 적어 놓아 똑같은 작은 문제가 나타날 경우 앞서 메모한 작은 문제의 결과 값을 이용하는 방법론입니다.

 

이러한 동적 프로그래밍을 풀 수 있는 조건은 다음과 같습니다.

• 작은 문제가 반복적으로 발생하는 경우
• 중복 문제들 끼리는 동일한 정답을 내 놓는 경우 [이게 바로 Divide and Conquer와의 차이점]

 

동적 프로그래밍은 이러한 중복을 효율적으로 처리하기 위해 기록을 해 놓는데 그 기록하는 것을 Memoization이라고 합니다.

 

흔히 memo={} 해서 알고리즘에서 많이 풀었던 테크닉이 바로 이 논리임!

 

대표적인 예제인 피보나치 예제를 통해 한번 살펴보도록 하자..!

def fib(n) : 
	if n == 1 or n == 2 : 
		return 1
	return fib(n-1) + fib(n-2)

피보나치 수열의 시간 복잡도는 본래 2^n의 지수 복잡도를 가지므로 매우 복잡도가 큰 알고리즘이다.

 

하지만 다음과 같이 Memoization을 사용하여 문제를 풀게 되면

def fast_fib(n, memo={}) : 
	if n in memo : 
		return memo[n]
	if n == 1 or n == 2 : 
		return 1
	result = fast_fib(n-1, memo) + fast_fib(n-2, memo)
	memo[n] = result
	return result

시간 복잡도는 O(n)으로 linear time이 된다..!