다이나믹 프로그래밍

중복되는 연산을 줄이기 위한 동적 계획법(DP)

👏메모리 공간을 약간 더 사용하여 연산속도를 비약적으로 증가시킬수 있는 방법

메모이제이션이란 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법. 메모이제이션이 동적 프로그래밍 중 하나

수학자들은 점화식을 사용해 다음과 같이 수열의 항이 이어지는 형태로 간결하게 표현한다.

이를 해석하면,
1번째 피보나치수 =1 , 2번째 피보나치수 =1

n 번째 피보나치 수 =( n-1 ) 번째 피보나치 수 + (n-2)번째 피보나치 수

이러한 수열을 배열이나 리스트로 표현한다.

피보나치수열을 재귀를 통해 구할 수 있지만 이는 비효율 적이며 굉장히 많은 연산이 필요하다.

🤷‍♂️ 다이나믹 프로그래밍을 사용할 수 있는 조건

1.큰 문제를 작은 문제로 나눌 수 있다.
2.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

큰 문제를 작게 나누는 방법에서 분할 정복과 비슷하다고 생각할 수 있는데 다이나믹 프로그래밍과의 차이점은 DP는 문제들이 서로 영향을 미치고 있다는 점이다.

🙌 DP의 구현방법

Top-Down(하향식) 방식

큰 문제를 해결하기위해 작은 문제를 호출한다.
재귀 함수를 사용

Bottom-Up(상향식) 방식

피보나치 수열문제에서와 같이 아래에서 위로 올라가는 방식
이때 사용되는 결과 저장용 리스트를 'DP테이블' 이라 한다.

🌹문제 접근 방법

1. 완전 탐색 알고리즘으로 접근했을때 시간이 매우 오래걸린다? ==> 다이나믹 프로그래밍 유형임을 파악

2. 단순 재귀함수로 구현하였을때(탑다운) 문제에서 그대로 사용 될 수 있다면 코드를 약간 개선

3. 가능하다면 탑다운 방식 보다는 보텀업 방식을 통해 구현
   (시스템상 재귀함수의 스택 크기가 한정되어 있을 것이다)