동적계획법과 분할정복

정의

동적 계획법 (DP: Dynamic Programming)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근법, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• Memoization 기법 사용
• ex) 피보나치 수열

 

분할 정복 (Divide and Conquer)

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위 해답을 구하는 방식 -> 일반적으로 재귀함수로 구현
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
• ex) 병합 정렬, 퀵 정렬 등

 

공통정과 차이점

공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할

차이점

• 동적 계획법
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
  • Memoization 기법 사용
• 분할정복
  • 부분 문제는 서로 중복되지 않음