모각코 3회차 : 동적 계획 Dynamic Programming

동적 계획 Dynamic Programming

"최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 구하는 설계 기법이다."

DP는 기본적으로 사전 계산된 값들을 재활용하는 식이다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고.

이런 방식을 이용하기 때문에 DP는 계산 횟수를 줄여주기에 효율적이다.

 

DP는 기본적으로 분할 정복 알고리즘이랑 비슷하다.

문제를 잘게 잘게 쪼개어, 쪼갠 문제들의 답을 구하고 이 답을 이용하여 원래 문제의 답을 찾는 방식이다.

여기서 주어진 문제의 답을 한 번만 계산하고 저장한 뒤, 문제를 이용할 때 저장해둔 답을 바로 산출하여 이용하기 때문에

DP에서 속도를 향상시킬 수 있는 것이다.

 

예시 1 : 1003 : 피보나치 함수

 

코드

#include <stdio.h>

int fibo(int n) {
    int a;
    int arr[41] = {0, };
    arr[0] = 0;
    arr[1] = 1;
    for (a = 2; a <= n; a++) {
        arr[a] = arr[a - 1] + arr[a - 2];
    }
    return arr[n];
}

int main() {
    int n, t;
    scanf("%d", &n);
    for (int a = 0; a < n; a++) {
        scanf("%d", &t);
        if (t == 0)
            printf("%d %d\n", 1, 0);
        else if (t == 1)
            printf("%d %d\n", 0, 1);
        else
            printf("%d %d\n", fibo(t - 1), fibo(t - 2));
    }
    return 0;
}
//
// Created by Leehyuntae on 2025-07-21.
//