다이나믹 프로그래밍 Dynamic Programming

---

다이나믹 프로그래밍 Dynamic Programming

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

동적 계획법 이라고 표현하기도 함.

• 탑다운(Top-Down) 방식 

      - 재귀함수 이용

      - 큰 문제를 해결하기 위해 작은 문제를 호출

      - 하향식

• 보텁업(Bottom-Up) 방식

      - 반복문 이용

      - 작은 문제부터 차근차근 답을 도출

      - 상향식 

---

DP 테이블

- 보텁업 방식에서 사용되는 결과 저쟝용 리스트

- 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현

   * 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념

---

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시 : 피보나치 수열

1   1   2   3   4   5   13   21   34   55   89