[ 알고리즘 ] 다이나믹 프로그래밍 (DP)

우선 재귀함수에 대해 이해를 하고 가야한다.

 

피보나치 수열로 예를 들어보자

15번째 값을 구하려면 14,13번째 값을 알아야한다.

14번재 값을 구하려면 13,12번째...

이렇게 13번째 연산이 반복된다. 

(출처)유튜브 동빈나

 

재귀함수는 이미 해결한 문제를 다시 반복해서 해결하기 때문에 비효율적이다.

 

이럴 떈 다이나믹 프로그램을 사용한다.

단, 가정이 필요하다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그걸 포함하는 큰 문제에서도 동일하다.

 

 

우선 피보나치 수열을 예시로 분석해보자

 

[ 재귀 함수 ]

 

이렇게 구현하는 경우에는 했던 계산을 또 해야하는 비효율성이 생기고

그로 인해 시간이 오래 걸리므로 필요가 없다.

 

 

[ 다이나믹 프로그래밍 ]

 

 

int d [ 100 ];

if ( d [ x ] ! = 0 ) return d [ x ]; 

return d [ x ] = dp( x - 1 ) + dp( x - 2);

 

세 개만 바꿔주면 비효율성은 사라진다.

 

계산했던 것들이 있으면 그 값을 그대로 가져와서 사용하기 때문에 

한 번 계산이 완료된 것들은 다시 계산되지 않는다.

 

 

[ 요약 ]

다이나믹 프로그래밍이란?

: 재귀 함수에서 반복해서 계산 및 동작하는 것들이 만들어내는 비효율성을 줄이는 방법

   ▶ 계산한 건 저장해두고, 필요할 때 꺼내쓴다 (다시 계산 X)

 

 

---

---