1. 정의

큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법.
기억하기

분할정복과의 차이점

분할정복과 동적 프로그래밍 모두 큰 문제를 작은 여러 개의 문제로 나누어서 해결하는 기법인데, 분할 정복은 작은 문제들이 반복되지 않지만, 동적 프로그래밍은 작은 문제에서 반복되는 부분이 발생하여, 그 값을 저장해 두었다가 이용한다는 점이 다름. 따라서 기억하기 프로그래밍이라고 부르기도 함. (동적이라는 단어와는 큰 연관성이 없음)

다시 말하면, 동적 프로그래밍은 동일한 문제는 한 번만 풀도록 하는 기법을 의미. 분할 정복의 경우에는 동일한 문제를 반복해서 푸는 경우도 발생하고 이는 비효울성을 초래.

2. 조건

1) 큰 문제를 작은 문제로 분할 할 수 있음.(= 작은 문제들이 반복됨)
2) 작은 문제들의 답은 항상 동일
=> 메모이제이션을 이용함

memoization(메모이제이션)

이미 계산한 결과(작은 문제 해결 시)를 배열에 저장하여 재사용하는 방법

3. 예시

1) 피보나치 수열 - 효율 비효율 다시공부필요!!

• #### 비효율적인 코드

//동적 알고리즘을 사용하지 않은 경우 - 배열할당한 경우
//num이 커질수록 반복 계산이 크게 늘면서 속도가 크게 저하됨. 
function solution(num){
  var answer = 0;
  var memo = [];
  
  memo[0]=1;
  memo[1]=1;
  
  for(var i=2; i<num; i++){
    memo[i] = memo[i-1] + memo[i-2];
  }
  
  answer = memo.pop();
  return answer;
}

//동적 알고리즘을 사용하지 않은 경우 - 재귀함수 이용
//num이 커질수록 반복 계산이 크게 늘면서 속도가 크게 저하됨.
function solution(num){
  if (num < 2){
  	return 1;
  }
  return solution(num-1) + solution(num-2);
}

효율적인 코드 - 동적알고리즘의 메모이제이션 활용한 경우(Q-코드 확인 필요)

//동적 알고리즘을 사용한 경우 -> 이건 동적이 아니라 그냥 반복문???
function solution(num){
 var answer = 0;
 var memo = [0,1];

  if(num < 2){
    return memo[num];
  } else{
    for(var i=2; i<=num; i++){
      memo.push(memo[i-1]+memo[i-2]);
    }
  } 
  answer = memo.pop();
  
  return answer;

}

//동적 알고리즘을 사용한 경우 
function solution(num){
 var answer = 0;
 var memo = [0,1];

  if(num < 2){
    return memo[num];
  } else{
    memo[num] = 
  } 
  answer = memo.pop();
  
  return answer;

}

2) 다른 예제들