동적계획법

동적계획법 DP 란?

다이나믹 프로그래밍 이라고도 불리며,

하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나눠서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정.

 

문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘 설계 기법.

 

동적계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있음.

 

전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해

전체 문제를 해결하는 방식이라고 볼 수 있음.

 == > 규칙을 찾는 게 관건. !

 

동적 계획법 접근 방법

1) Bottom Up 방법

작은 문제에서 큰 문제로 반복문 호출

 

2) Top Down 방법

큰 문제에서 작은 문제로 재귀 호출

 

 

-  메모이제이션 : 중복된 계산을 방지하기 위해 앞 계산을 어딘가에 저장해 필요할 때 불러오는 기법

      -- > 배열 혹은 해시를 활용하는 것이 핵심.