동적 계획법( Dynamic Programming) 과 분할 정복(Divide Conquer)

동적 계획법 ( DP; Dynamic Programming) ?

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해 보다 큰 크기의 부분 문제를 해결
• 상향식 접근법
• Memoization 기법 : 프로그램 실행 시, 이전에 계산한 값을 저장하여 다시 계산하지 않도록 함 -> 실행속도 향상
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨 -> 피보나치 수열                                                                                                                                         

분할 정복 (Divide and Conquer ) ?

• 문제를 나눌 수 없을 때까지 나누어서, 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법 (일반적으로 재귀함수로 구현)
• 문제를 잘게 조갤 때, 부분 문제는 서로 중복되지 않음                                                                                                        

 

 

공통점과 차이점

• 공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    • Memoization 기법 사용(부분 문제의 해답을 저장해서 재활용하는 최적화 기법)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않음
    • Memoization 기법 사용 안함