210705 동적 계획법(Dynamic Programming, DP)

동적 계획법(Dynamic Programming, DP) vs 분할 정복법(Divide and Conquer)

 

문제를 분할하여 작은 문제로 만들어 해결한 후 합쳐서 문제 해결하는 것은 동일
동적 계획법은 서브 문제들 간의 관계가 존재하여 overlapping (작은 문제들이 중복되는 일) 발생 => 작은 문제들의 결과 저장하여 다시 계산하는 일 생략	서브 문제들간의 overlapping 없음

최적 부분구조(Optimal Substructure) 

전체 문제가 최적(optimal)구조가 되려면 그 서브 문제들도 최적화 된 솔루션으로 해결가능 해야 함. 

=> 문제를 해결할 때 서브 문제들을 해결하여 그 결과들을 이용하여 최종적인 답 구함

이러한 구조를 가진 문제로 대표적인 예가 최단 경로 문제

 

피보나치

210625 시간복잡도와 공간복잡도 :: Registro (tistory.com)

210625 알고리즘 분석

에서 피보나치 수열을 구하는 알고리즘의 시간복잡도 구하는 것을 하였으니 재귀랑 반복문은 간략화함

• 재귀
  • 시간 : O(N^2)
  • 공간 : O(N)
• 동적 계획법(DP) - Memoization

  int f[N] ={-1};
  
  int fib(int n){
  	if(n==0) return 0;
  	if(n==1) return 1;
      if(f[n] > 0) return f[n]; //미리 계산된 것 반환
      
      else{
      	f[n] = fib(n-1) +fib(n-2);
      	return (f[n]);
      }
  }​

  3번째 if 문에서 이미 계산되어 있으면 순환 호출을 하는 것이 아니고 배열에 저장한 값을 반환하여 overlapping(중복)을 없애는 것이 핵심
  
  • 시간 : O(N)
  • 공간 : O(N)
• 동적 계획법(DP) - Bottom up

  int f[N] ={0};
  
  int fib(int n){
  	f[0]=0;
      f[1]=1;
      
      for(int i=2;i<=n;i++){
      	f[i]=f[i-1]+f[i-2];
      }
      return (f[n]);
  }

  
  
  • 시간 : O(N)
  • 공간 : O(N)

• 반복문
  • 시간 : O(N)
  • 공간 : O(1)

 

 

Matrix-Chain Multiplication 

목표 : 모든 행렬을 곱하지만 최소한의 곱셈 횟수로 결과를 계산하는 것

ex)

DP식 해결 방식 == 최적의 괄호들이 합쳐지면 최적의 방법 

 

이후 계산 과정은 좀 지저분하지만... 

 

이런 과정을 통하여 최적의 곱셈 순서는 (A X B) X (C X D) 으로 결정된다.