[알고리즘] Dynamic programming - Fibonacci number, Floyd-Warshall algorithm
다이나믹 프로그래밍: 중복 계산을 피하는 지혜 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장해두었다가 재활용하는 알고리즘 설계 기법이다. 분할 정복 알고리즘과 유사하지만, 중복되는 부분 문제들을 저장하고 재사용한다는 점 에서 큰 차이가 있다. 이러한 특징을 가장 잘 보여주는 예시가 바로 피보나치 수열이다. 피보나치 수열 계산: 재귀 vs 다이나믹 프로그래밍 피보나치 수열은 다음과 같은 점화식으로 정의된…