[이코테] 다이나믹 프로그래밍

다이나믹 프로그래밍 컴퓨터를 사용한 문제 해결에 있어서, 일반적으로 효율적인 설계라 함은 연산속도나 메모리 공간을 줄여나가는 것이다. 그러나 본 장에서 배울 다이나믹 프로그램과 같이, 조금의 메모리 공간을 더 할애하여 비약적인 성능을 끌어낼 수 있는 경우도 존재한다. 이를 동적 계획법이라고도 부르며, 프로그래밍에서 사용되는 동적 할당의 의미와는 다르다는 것을 인지할 필요가 있다. 다이나믹 프로그래밍의 대표적인 유형으로는 피보나치 수열이 존재한다. 이전 두 항의 합을 현재 항으로 설정하는 특징을 갖는 수열이다. 수학적인 표현으로 점화식을 사용하지만, 프로그래밍에서는 배열이나 리스트를 사용한다. 파이썬에서는 리스트를 사용한다. 이를 구현하기 위해서는 재귀 함수를 사용하면 된다. 재귀 함수를 이용한 피보나치 ..

원문링크 : [이코테] 다이나믹 프로그래밍