동적 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 푸는 최적화 기법이다. 이는 같은 상황이 반복되는 경우에 매우 효과적이다. 동적 프로그래밍은 똑같은 하위 문제를 여러번 계산하지 않기 위해 결과를 저장해두고 이를 재활용하는 방식으로 진행된다. 동적 프로그래밍의 간단한 예시로 피보나치 수열이 있다.피보나치 수열의 경우 재귀함수로 간단하게 구현할 수 있지만 이렇게 될 경우 값을 구하기 위해 이전에 했던 계산을 다시 하면서 비효율적으로 동작한다.int fib(int n) { if (n n이 만약 10이라면 값을 구하기 위해 9,8일때의 값을 구해야한다. 또한 이를 구하기 위해선 각각8,7 7,6을 구해야한다. 즉 n값이 커질수록 연산수가 급격하게 늘어난다.하지만 이러한 반복 과정을 저장해서 사용..