동적프로그래밍

다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누고 효율적으로 푸는 방법이다. 효율적으로 풀기 위해서는 중복되는 작은문제에 대한 처리를 Memorization을 통해 간단히 해결할 수 있다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 큰 문제를 작은문제로 바꾸어 푸는 것이다. 다이나믹 프로그래밍으로 문제를 해결하기 위해서는 Overlapping Subproblem과 Optimal Substructure라는 두가지 조건을 만족해야한다. 그리고 위의 조건에 의해 불필요하게 중복처리해야하는 문제들이 있다. 이를 해결하기 위해 Memorization을 사용한다. 다이나믹 프로그래밍의 대표적인 예로 피보나치 수열이 있으며 다이나믹 프로그래밍의 두가지 조건과 효율적으로 해결하기 위한 Memoriation을 알아보도록..