동적계획법(Dynamic Programming, DP) - Python

동적 계획법 (動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. (위키피디아)

• 입력 크기가 작은 문제를 해결한 다음 보다 크기가 큰 부분 문를 해결한 다음 그것을 결합하며 최종적으로 전체 문제를 해결하는 상향식 접근 알 고리즘이다.
• Memoization기법을 사용 : 이전에 사용한 값을 저장하여 다시 계산하지않는다.
  • 이렇게 각 계산값을 저장하게 되면 중복 계산 시간이 줄어든다.
• 부분 문제는 중복되어 재활용된다
  • 대표적인 예로 피보나치 수열
  • 재귀로 푸는 것도 물론 가능하지만 중복되는 연산을 줄일 수 있는 점에서 아주 효과적임

  def fibo(n):
  	cache = [0 for index in range(n + 1)]
  	cache[0] = 0
  	cache[1] = 1
  
  	for i in range(2, num + 1):
  		chche[index] = cache[index - 1] + cache[index -2] # memoization
  		return cache[n]
  

• 일반적으로 재귀로 푸는것보다 훨씬 빠르다
  • 통상적으로 코드도 간단
• 점화식패턴을 찾아 풀어야함! 
  • 다양한 문제를 보면서 점화식을 도출해내는 방식을 연습해야함

동적계획법 백준 문제 연습하기