다이나믹 프로그래밍

• 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
  -이미계산된 결과(작은문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
  -다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운/보텀업)으로 구성된다.

• 다이나믹 프로그래밍은 동적 계획법이라고도 부른다.
  일반적인 프로그래밍에서 동적이란) 프로그램이 실행되는 도중에 이지만 다이나믹프로그래밍에서의 '다이나믹'은 별다른 의미 없이 사용 된 단어.

• 다이나믹 프로그래밍은 다음의 조건이 만족할 때 사용한다

1. 최적 부분구조
   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할수있을때.
2. 중복되는 부분 문제
   동일한 작은 문제를 반복적으로 해결해야 할때.

피보나치 수열 코드 예시)

x==1 or x==2 로 종료조건 설정 하면 값 을 구할수 있다.

하지만 이렇게 한다면 숫자가 커질수록 중복되는 숫자가 급격하게 많아진다. 피보나치 수열을 확인해보면 다이나믹 프로그래밍의 사용 조건 1,2 번을 만족하는것을 알수있는데. 다이나믹 프로그래밍을 이용항여 시간 복잡도를 최적화 시켜야한다.

하향식 다이나믹 프로그래밍(탑 다운)

큰문제 ( 탑) 를 해결하기 위해 작은문제(다운)를 재귀적으로 호출하여 큰문제를 해결

• 메모이제이션
  한번 계산한 결과를 메모리 공간에 메모하는 기법이다.

1. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
2. 값을 기록해 놓는다는 점에서 "캐싱" 이라고도 한다.
3. 메모이제이션 기법은 다이나믹 프로그래밍에만 국한된 개념은 아니다.

탑 다운 코드 예시)

상향식 다이나믹 프로그래밍(보텀 업)

보텀 업 코드 예시)

보텀업은 작은문제들로 큰 문제를 해결 할 수 있으므로 작은문제들을 반복적으로 수행하여 큰 문제를 해결 한다. 이를 위한 초기 값을 설정