28391 다이나믹 프로그래밍(동적 계획법) ex)백준 2839번 -python 다이나믹 프로그래밍 dynamic programming, DP 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘에 유리 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 예로 피보나치 수열, 점화식, 최단 경로 문제, 행렬의 제곱 문제 등 최적화에 사용 이미 계산한 결과를 별도의 메모리에 저장하여 다시 계산하지 않아 수행시간 효율이 좋다. ex) 피보나치 function fib(n): if n = 0: return 0 elif n = 1: return 1 else: return fib(n - 1) + fib(n - 2) 재귀함.. 2022. 10. 28. 이전 1 다음