프로그래밍을 하다보면 규모가 큰 문제를 풀어야 하거나 다뤄야 하는 경우가 생긴다.
이런 경우 문제를 더 효율적으로 다루기 위해 사용하는 방법이 바로 Dynamic Programming이다.

📒Dynamic Programming(DP)

✍Dynamin Programming이란?

복잡하고 큰 문제를 여러개의 간단하고 작은 문제로 나누어 푸는 방법

✍방법

1. 큰고 복잡한 문제를 여러개의 간단한 작은 문제로 나눈다.
2. 작은 문제부터 시작하여 큰 문제를 해결하는 방법으로 푼다.(BOTTOM-UP)
   • 작은 문제의 결과를 저장하여 기억하고, 큰 문제를 풀다 필요하다면 다시 꺼내어 쓴다.
   • 한번 푼 문제는 다시 풀지 않는다.

📌 BOTTOM-UP

작은 문제부터 차례로 푸는 방법, 반복문을 사용하는 경우가 많다.

구현

(Fibonacci 수열)

int fibonacci(int n)
{
	int fir=0;
    int sec=1;
    for(int i=2; i<=n; i++){
    	next=fir+sec;
        fir=sec;
        sec=next;
    }
    return next;
}

📌 TOP-DOWN

BOTTOM-UP 방법과 반대되는 방법, 재귀함수로 문제를 푸는 경우가 많다. 큰 문제를 풀 때 작은 문제가 필요하다면 그때 작은 문제를 푼다.
Dynamic programming 방법이 아니다.

구현

(Fibonacci 수열)

int fibonacci(int n)
{
	if(n==0){
    	return 0;
    }
    else if(n==1){
    	return 1;
    }
    else{
    	return fibonacci(int n-2) + fibonacci(n-1);
    }
    return -1;					//오류의 경우
}

✍조건

• 작은 문제의 반복이 일어나는 경우.
  - 분할정복과의 차이점이다. 분할 정복은 작은 문제의 반복이 없다.
• 같은 문제는 항상 정답이 같다.
  -하나의 문제는 단 한번만 푼다.
  

📒Memoization

✍Memoization이란?

동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장함으로 반복 수행을 제거하고 실행 속도를 빠르게 한다.

동적 프로그래밍에서 작은 문제들의 정답을 메모리에 저장하고 다시 사용함으로써 프로그램의 실행 속도를 빠르게 한다.

✍구현

(Fibonacci 수열)

int fibonacci(int n)
{
	int arr[1001];
    arr[0] = 0;
    arr[1] = 1;
    
    for(int i=2; i<=n; i++){
    	arr[i] = arr[i-2] + arr[i-1];
    }
    
    return arr[n];
}

큰 문제들을 Dynamic Programming과 Memoization을 활용하여 효과적을 해결할 수 있다.