8. 동적계획법(DP)

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.
여기서 어떤 부분 문제는 같은 문제를 두 번 이상 풀 수도 있기 때문에, 이 문제에서 답을 여러 번 계산하는 대신
한번만 계산 하고 계산 결과를 저장해 놓고 재사용한다.
따라서 속도의 향상을 꾀할 수 있다.

중복되는 부분 문제

cache - 이미 계산한 값을 저쟁해 두는 메모리 장소
overlapping subproblems - 중복 되는 부분 문제

 

 

ex)

대표적인 문제 - 이항계수

조합 nCr, \( \begin{pmatrix} n \\ r \end{pmatrix} \)은 다음과 같은 성질이 있다.

메모이제이션

memoization - 한 번 계산한 값을 저장해 두었다가 재활용하는 최적화 기법

 

위와 같은 이항계수 문제를 일반적인 재귀함수로 풀면,

함수호출이 2의 n승으로 불어난다.

 

하지만, 한 번 계산한 값을 배열에 저장해두고, 그 계산을 반복하지 않게 하면서 이전에 저장한 값을 이용한다면,

n의 제곱꼴로 증가하게 되어, 함수 호출을 줄일 수 있다.