동적 프로그래밍 개념

  동적 프로그래밍 

동적 프로그래밍 개념

큰 문제의 해답에 작은 문제의 해답이 포함되는 알고리즘을 재귀적으로 처리할 때 나타나는 비효율을 제거하기 위한 프로그래밍 방식을 동적 프로그래밍이라고 한다.

 

가령 피보나치수열의 경우 다음과 같은 식으로 나타난다.

---

f(n) = f(n-1) + f(n-2)

f(1) = f(2) = 1

---

 

이를 재귀적으로 해결하기 위해서는 기존에 구했던 해답을 다시 구하는 등의 반복이 일어난다.

 

쉽게 배우는 알고리즘 동적 프로그래밍 그림 8-1

 

이러한 문제를 해결하기 위해 부분 결과를 저장하면서 해를 구하는 것이 동적 프로그래밍의 핵심이다.

가령 위에서 설명한 피보나치수열의 문제를 동적 프로그래밍을 적용해 해결한다면 다음과 같이 풀 수 있다.

 

피보나치수열 알고리즘

fib(n)
{
    if (f[n] ≠ 0) then return f[n];
    else {
        if (n = 1 or n = 2)
        then f[n] ← 1;
        else f[n] ← fib(n - 1) + fib(n - 2);
        return f[n];
    }
}

 

https://github.com/NadanKim/Algorithm

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘