다이나믹 프로그래밍(동적 계획법) 이란 ? : 컴퓨터 연산을 하면서 중복되는 연산을 줄이자는 목적으로 나온 기법이다. 보통, 다이나믹이라고 하면 '프로그램이 실행되는 도중에' 라는 의미로 쓰이는데(ex.동적할당), 여기서는 그런 의미는 아니다. 연산을 줄이자는 것이 목적이라면, 재귀함수로 프로그램을 짤 수도 있는 것 아니냐고 생각할 수 있다. 물론, 할 수는 있다. 하지만, 수가 크다면, 실행시간은 기하급수적으로 늘어나기 때문에, 계속해서 재귀함수를 호출하는 것은 컴퓨터에 많은 부하를 줄 수 있다. 예를 들어, 피보나치 수열을 재귀함수로 구현한다면, n이 100 이기만 해도, 연산 횟수가 약 1,000,000,000,000,000,000,000000,000,000번이다. 즉, 1초에 1억번 정도의 연산을..
