동적 게획법

복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법

• 상향식 접근법으로 가장 최하위 해답을 구하고, 공간을 할당하여 기억하고 해당 결과값을 이용해 상위 문제를 풀어간다.
• 문제를 해결하기 위한 모든 방법을 검토하고, 그 중 최적의 풀이법을 찾아낸다.
• ex. 피보나치 수열

방법

1. 입력 크기가 작은 부분 문제들을 해결한다.
2. 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결한다.
3. 최종적으로 전체 문제를 해결한다.

분할 정복 - Divide and conquer

문제를 나눌 수 없을 때까지 나누어 다시 합병하여 문제의 답을 얻는 알고리즘

• 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식이다.

  일반적으로 재귀함수로 구현한다.

• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않는다.

  병합 정렬, 퀵 정렬 등

공통점과 차이점

공통점

문제를 잘게 쪼개서 가장 작은 단위로 분할한다.

차이점

동적 계획법

• 부분 문제는 중복되어, 상위 문제 해결시 재활용된ㅇ
• Memoization 기법이 사용된다.

분할 정복

• 부분 문제는 서로 중복되지 않는다.
• Memoization 기법은 사용되지 않는다.