반응형
다이나믹 프로그래밍 분할정복 차이
-
Dynamic Programming (동적계획법)Algorithm/Source Code 2021. 11. 7. 18:16
DP ? " 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 " 이런 문제에 활용해요 ! 큰 문제를 작은 문제로 나눌 수 있다 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다 최적성의 원리를 만족하는지 판단 최석성의 원리란 ? 주어진 문제의 부분해가 전체 문제의 해를 구하는데 사용되는지를 의미한다 피보나치 수열로 이해하기 DP 의 가장 좋은 예시인 피보나치 수열이 있다 F(n) 을 구할 때 트리를 보면 f(n-3) 연산식이 여러 번 사용되는데 상위 문제인 F(n) 을 구하기 위해서 여러 소문제들이 사용된다는 것을 알 수 있다 자주 사용되는 소문제들이 존재할 경우 자원의 낭비를 막기위해 " 동적프로그래밍에서는 소문제의 해를 저장" 해두고 사용하게 된다 ! 중복 연산을 방지하기 위..