1. 동적계획법(Dinamic Programing)

1.1 조건

1) 해결해야 하는 문제를 여러개로 쪼갤 수 있는가
2) 쪼개진 문제들로 더 큰 문제를 해결할 수 있는가
3) 쪼개진 해결방법 중 겹치는 것이 있는가

1.2 대표적인 문제: 피보나치

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

• 재귀 ver
  

• 그림으로 보기
  

2. 분할정복

어떤 문제를 해결하려고 할 때 문제를 해결하기 위해 쪼개고 쪼갠 문제를 해결해서 원래의 문제를 해결하는 것

2.1 분할 정복의 과정

1) Divide : 기존 문제를 작은 부분문제들로 나눔
2) Conquer : 각 부분 문제를 해결

• 이 과정에서 Divide, Conquer, Combine 과정이 반복 (재귀)

3) Combine : 부분 문제들의 솔루션을 통해 기존 문제를 해결

• Base Case : 이미 문제가 작아서 더 작은 문제로 나누지 않아도 답을 알 경우
• Recursive Case : 문제가 커 답을 바로 알 수 없어서 더 작은 문제로 나눠야 할 경우(Divide 해야 할 경우)

3. 동적계획법과 분할정복의 차이

동적계획법	분할정복
중복 부분 문제가 있을 때 최적 부분 구조가 있을 때	제약 없음
기록해서 재사용(Top-Dowm) 테이블을 이용(Bottom-Up)	제약 없음

참고 자료

• 동적계획법
• 분할정복
• 동적계획법과 분할정복의 차이