Dynamic programming (동적 계획)

// Dynamic programming 

---

   What is Dynamic programming?   

  <Dynamic programming>이란, 문제의 입력사례를 분할하여 문제를 푸는 것이다. 흔히들 'DP'라고 많이 한다. 이 점은 분할정복과 비슷하지만, 분할정복은 Top-down(하향식) 접근방법이고 <Dynamic programming>은 Bottom-up(상향식) 접근방법이다. 

  또한 <Dynamic programming>의 특징은 이미 계산된 부분 문제가 다시 발생하면 또 계산을 하는 것이 아닌 이전의 계산값을 참조한다는 것이다. 

---

   Example   

  우리는 <Dynamic programming>의 예시로 <Fibonacci sequence>를 들 수 있다. 좌측 삽입한 링크에 들어가면 <Dynamic programming>을 사용하여 <Fibonacci sequence>를 구현한 예시를 볼 수 있다.

---

"Top-down(하향식) 접근방법 이란?"

* 큰 문제에서 작은 부분문제를 재귀적으로 호출하여 리턴 되는 값을 이용하여 큰 문제를 해결하는 방식

"Bottom-up(상향식) 접근방법 이란?"

*  작은 부분문제들을 미리 계산해두고, 이 부분문제들을 모아 큰 문제를 해결하는 방식

---

글 작성을 위해 <Code ground, www.codeground.org/>사이트와 <알고리즘 기초, Neapoitan 저>책을 참고하였습니다.

 

// 작성중인 글 입니다.