전북대학교 알고리즘 합병정렬 5조 안준철

1. 동적프로그래밍 VS 분할정복법

분할정복법

• 문제를 독립적인 부분 문제로 분할하고 부분 문제를 재귀적으로 해결 한 후 결과물을 결합하여 원래의 문제를 해결하는 방식
• 문제의 맨 상위 사례의 해답은 아래로 내려가서 작은 사례에 대한 해답을 구함으로써 얻을 수 있는 방식이므로 하향식(top-down) 접근방법임

• 장점 : 코드를 작성하기 쉽고 직관적임

           분할 한 부분 문제가 서로 독립적일 때 효율적

• 단점 : 분할한 부분 문제들이 다시 자신의 부분 문제를 공유할 때 문제들을 중복 계산하여 Time Complexity가 증가함

동적프로그래밍

• 작은 사례를 먼저 해결하고 그 결과를 테이블에 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 대신 그 저장한 결과를 이용함
• 다시 수행이 요구될 때 또 수행하는 것이 아니라 이전에 기록된 결과를 이용하는 것이 핵심
• 부분 문제들이 서로 독립적이지 않을 때(부분 문제들이 다시 자신의 부분 문제를 공유할 때) 적용
• 상향식(bottom-top) 접근방법

한번 해결 한 부분문제를 저장하여 나중에 다시 사용한다면 더욱 효율적인 알고리즘이 됨

programming 이라는 말은 컴퓨터 프로그램과 무관하고 표를 이용하는 방법이라는 뜻

1.  
2. 분할정복법
3. int Fib (int n)
   {
    if (n <= 1)
     return n;
    else
     return Fib(n-1) + Fib(n-2);
   }
4.  
5. 동적프로그래밍
6. int dynamicFib (int n)
   {
       index i;
       int f[0..n];
       f[0] = 0;
       if (n > 0)
7.     {
           f[1] = 1;
           for (i=2; i<=n; i++)
               f[i] = f[i-1] + f[i-2];
       }
       return f[n];
   }

출처:

http://alg.devlife.net/Algorithms/DynamicVSDivide.aspx
http://alg.devlife.net/Algorithms/DynamicVSDivide.aspx
http://alg.devlife.net/Algorithms/DynamicVSDivide.aspx

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

• 전북대학교 알고리즘 합병정렬 5조 - 알고리즘 & 자료구조 by prettyhip