다이나믹 프로그래밍

샤핑

 

 

이번 시간에는 다이나믹 프로그래밍에 대해서 살펴보겠습니다.

 

 

 

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법) - "예전에 만든 것을 재활용하자!"

- 과거에 구한 해를 활용해서 효율적으로 값을 구하는 기법입니다.

- '예전에 저장한 값을 다시 사용하는 기법'이라고 이해하면 됩니다.

 

 

가장 대표적인 예시: 피보나치 수열에서 n번째 값 계산

피보나치 수열은 1,2번째 값을 1로 둔 상태에서 앞의 두 값을 계속 합해나가는 수열입니다. 이 수열의 n번째 값을 구하려면, 배열에 합계를 계속 저장한 후 n번째 값을 배열에서 가져와야 합니다. 물론, 재귀함수를 활용할 수도 있지만, 다이나믹 프로그래밍 기법을 사용하기 위해서 배열을 선택하였습니다. 소스 코드는 아래와 같습니다.

 

 

출력 결과) 수열의 n번째 값: 5

※ 실행하면 배열에 [1, 1, 2, 3, 5] 라고 저장됩니다. 여기서, 배열의 5번째 값 '5'를 출력하면, 수열의 5번째 값을 구할 수 있습니다.

 

 

<출처>

나무위키: 동적 계획법

소스 코드: https://github.com/jhs951101/DP