[알고리즘 이론] 동적 계획법(Dynamic Programming)

동적 계획법(DP, Dynamic Programming)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결. 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근으로, 가장 최하위 해답을 구한 후 이를 이용해서 상위 문제를 풀어가는 방식
• 문제를 잘게 분할할 때, 부분 문제는 서로 중복되어 재활용됨
• Memoization 기법 사용

(참고) 분할 정복이란?

• 문제를 나눌 수 없을 때까지 각각 나누어서 풀고, 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근 방법 (일반적으로 재귀 함수로 구현)
• 문제를 잘게 분할할 때, 부분 문제는 서로 중복되지 않음(ex. 병합 정렬, 퀵 정렬)

 

 

예시) 피보나치 수열

# recursive call 사용
def fibo_with_recursion(num):
	if num <= 1:
		return num
	return fibo_with_recursion(num-1) + fibo_with_recursion(num-2)

# DP(동적 계획법) 사용
def fibo_with_dp(num):
	cache = [0 for i in range(num+1)]
	cache[0] = 0
	cache[1] = 1
	
	for i in range(2. num+1):
		cache[i] = cache[i-1] + cache[i-2]
	return cache[num]

 

예시) 백준 11726. 2xn 타일링

[백준 baekjoon] 11726. 2xn 타일링