divide & conquer
<aside> 💡
복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는방법이다.
</aside>
→ 시간에 따라 해가바뀐다
큰 문제를 작은 문제로 나눈다.
작은 문제들이 반복돼 나타나며 작은 문제들의 결과값은 항상 같다.(작은 문제들은 이미 최적의 값을가지고있다.) 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용 할 때는 이 DP 테이블을 이용한다.
이를 (memoization)기법이라고 한다. 탑 다운(top-down) 방식 혹은 바텀 업(botton-up) 방식으로 구현 가능하다.
겹치는 부분 문제 : 동일한 작은 문제들이 반복하여 나타나는 경우 -> 점화식으로 표현이 가능하다.
(부분 문제가 반복되지 않는 경우 값을 재사용할 수 없기 때문에 부문 문제가 중복되지 않는 경우 사용이 불가능하다.)
최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
탑 다운 방식 → 주로 재귀 & 가독성 & 백트래킹(가지치기)
