(C언어)DP Dynamic Programming 설명

다이나믹 프로그래밍은 취업을 할려면 필수로 배워야 하는 함수 같았다.

다이나믹 프로그래밍을 쉽게 말하자면 계산횟수를 줄여주는 함수다.

아직 C언어를 제대로 배우지 못해 코딩을 많이 안해본 분들은 계산 횟수를 왜 줄여줘야 하는지 잘 모른다.

왜냐하면 그들이 만든 코딩은 대부분 숫자가 별로 없기 때문이다. 

하지만 for while과 같은 반복문을 사용할때 1부터 1000000까지가 범위이면, 계산횟수가 엄청나게 늘어나서 빌드 할때 엄청 느리게 된다. 

 

지금부터 DP를 설명하겠다.

 

DP를 가장 쉽게 설명할수 있는 방법은 바로 피보나치 수열이다.

보통 피보나치 수열은 밑에 적어놓은것 처럼 코딩한다.

function fib(n)

if n = 0 return 0

else if n=1 return 1

else return fib(n-1) + fib(n-2)

이때 fib(5)를 구하고자 한다면 

fib(5) = fib(4) + fib(3)

fib(4) = fib(3) + fib(2)......

이렇게 엄청나게 복잡하다.

 

DP함수는 이렇게 엄청나게 복잡하게 계산 해야하는것들을 쉽게 만들어준다.

1. 결과를 담을 수 있는 배열을 만들어라! EX) int result[100];

 

2. result[n] = result[n-1] + result[n-2]; 피보나치 수열일때는 입력한 값이 0이거나 1이면 앞에 적어놓은 공식이 작동하지 않으므로 

result[0] = 0;

result[1] = 1; 이렇게 조건식을 인지한 후, 따로 정의해줘야 한다.

 

3. for 반복문을 사용하면 편하게 할수 있다.

for( int i = 2; i<=n; i++)

{ 

result[i] = result[i -1] + result[i -2];

}

 

이렇게 하면, 이미 구한 값이면 이미 구한 값 자체로 반환 한다.

이 말을 쉽게 말하자면 for반복문이 2부터 n까지 반복되면서 2부터 n까지의 모든 피보나치 수열 값들이

result[100] 배열에 저장이 됐다.

 

그러면 컴퓨터가 계산을 할때 아까처럼 하나하나 복잡하게 계산하지 않고, result[5] = result[4] + result[3];

이렇게 쉽고 간단하게 계산 할수가 있다.

 

백준:https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

#include <stdio.h>
int fibo(int n)
{
    int a;
    int d[41];
    d[0] = 0;
    d[1] = 1;
    for (a = 2; a <= n; a++)
    {
        d[a] = d[a - 1] + d[a - 2];
    }
    return d[n];
}
int main()
{
    int num,s;
    scanf("%d", &num);
    for (int a = 0; a < num; a++)
    {
        scanf("%d", &s);
        if (s == 0)
            printf("%d %d\n", 1, 0);
        else if (s == 1)
            printf("%d %d\n", 0, 1);
        else
            printf("%d %d\n", fibo(s - 1), fibo(s));
    }
    return 0;
}