[자료구조/알고리즘] 동적계획법(Dynaminc Programming, DP)

less than 1 minute read

동적계획법

동적계획버은 큰 문제를 작은 문제로 나누어서 푸는 기법.
답을 여러번 계산하는 대신 한번만 계산.

메모제이션

동적계획법 알고리즘의 대표적인 예 중 하나는 이항계수(nCr).

이항계수는 n개 중에 K개를 선택하는 경우의 수를 구할 때 사용
보통 n!/(n-k)!*k!  로 계산하지만, 
이렇게 할 경우 많은 중복이 발생.  

중복된 계산을 막기 위해 저장된 결과를 배열(캐시)에 저장(캐싱한다),
다음에 계산이 필요할 때 저장된 값을 불러와서 중복을 없앤다.
따라서 시간 복잡도가 줄어들게 된다.

재귀와 같은 방식으로 위에서 아래로 내려오는 방식. 함수 호출을 줄이기 위해 메모제이션을 사용.

for문을 이용해서 처음값부터 다음값을 계산해 나가는 방식
f(1)부터 f(n)까지 올라가는 것을 의미.
이 방식으로 계산하는 테크닉을 다이나믹 프로그래밍이라고 함.

동적계획법 알고리즘은 최적값을 구할 때 사용.