다이나믹 프로그래밍 vs 분할 정복 비교. 공통점 차이점

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

 

---

다이나믹 프로그래밍과 분할 정복은 모두 '최적 부분 구조'를 가질 때 사용할 수 있다.
  - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결하는 상황.

 

 다이나믹 프로그래밍과 분할 정복의 차이점은 '부분 문제의 중복' 이다.
  - 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨.
  - 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음.

 

 

 

 다이나믹 프로그래밍 문제 접근법.
 >주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는게 중요.
 >그리디, 구현, 완전 탐색으로 문제를 해결할 수 있는지 검토한다.
 > 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍으로 고려함.
 

 

 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이
 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.
 > 일반적인 코테에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제된다. 

 

 예제 : 개미 전사. 1로 만들기, 병사 배치, 금광 탐색 , 화폐 구성,

 

---