Dynamic Programming1 동적 프로그래밍 (Dynamic Programming, DP) 이란? 나동빈님 유튜브 내용을 참고 하였다. 개요 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 구현 방식 Top down Bottom up 특정 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 예제. 피보나치 수열 피보나치 수열은 다이나믹 프로그래밍으로 효과적으로 계산 가능 점화식으로 표현할 수 있다. 점화식을 재.. 2023. 3. 14. 이전 1 다음
