문돌이 존버/프로그래밍 스터디
2021. 4. 20.
다이나믹 프로그래밍(DP)이란? 개념 잡기
본 글은 나동빈님의 "이것이 코딩테스트다"를 참고해서 제 공부 차원에서 기록한 것입니다. 다이나믹 프로그래밍(Dynamic Programming)이란 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 대표적인 방법이다. 다이나믹 프로그래밍에는 top-down과 bottom-up 2가지 방식이 있다. 다이나믹 프로그래밍을 본격적으로 알아보기 전 피보나치 수열에 대해 살펴보자. 아래는 재귀 함수로 피보나치 수열을 구현한 것이다. def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) 위와 같은 코드는 $f(n)$ 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어난다. 시간 복잡도가..
