다이나믹 프로그래밍

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 15장 문제풀이입니다 15. 동적 계획법 15-1. 동적 계획법 개념 동적 계획법은 전체 문제를 한 번에 해결하는 것이 아니라, 작은 부분 문제를 해결하고, 이것을 활용하여 전체 문제를 해결하는 방법 이 때 동적계획법이 효율적이려면 다음과 같은 조건들이 필요하다 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 함 (중복 부분 문제) 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 함 (최적 부분 구조) 점화식 세우기와 동적 계획법 동적 계획법으로 문제를 해결하는 절차는 다음과 같다 문제를 해결하는 해가 이미 있다고 가정 종료 조건을 설정 과정 1, 2를 활용해 점화식을 만든다 Fact(N): # 문제를 해결..