다이나믹 프로그래밍 개념 정리(탑다운(메모이제이션)/ 바텀업 시간복잡도 / 파이썬 구현)

다이나믹 프로그래밍 강의 내용 : https://www.youtube.com/watch?v=5Lu34WIx2Us 1. 개념 - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑 다운과 바텀 업)으로 구성된다. - 동적 계획법이라고도 부른다. - 점화식을 사용해 문제를 해결한다. * 점화식: 인접한 항들 사이의 관계식 * 점화식은 프로그래밍에서 재귀함수를 사용하면 구할 수 있다. * 수열은 배열이나 리스트를 이용해 표현할 수 있다. cf) 일반적인 프로그래밍 분야에서 동적이라고 이야기하는 것과는 약간 차이가 있다. ex) 자료구조에..

2021.07.09