[알고리즘]동적계획법(DP)의 개념

동적계획법의 개념 티끌모아 태산이라는 속담이 있습니다. 작은것들을 모아서 큰 것을 이룬다는 의미이지요. 동적계획법Dynamic Programming도 이와 유사한 문제해결기법 입니다. 한번에 풀기 어려운 문제를 여러개의 작은 문제로 쪼갠후, 이 문제들의 해를 활용해서 전체문제를 해결하는 방식입니다. 즉 동적계획법의 핵심은 2가지 입니다. 문제를 쪼개는 과정과, 이를 활용해서 전체문제를 해결하는 과정입니다. 점화식 세우기 동적계획법으로 문제를 해결하는 절차는 아래와 같습니다. 1. 문제를 해결하는 해가 이미 있다고 가정 합니다. 2. 종료조건을 설정 합니다. 3. 1.과 2.를 활용해 점화식을 세웁니다. 예시로 팩토리얼을 동적계획법으로 해결하는 절차를 한번 봅시다. 참고로 N 팩토리얼이란, 1부터 N까지 수들을 모두 곱한 값을 말합니다. [표] 팩토리얼에 대한 점화식을 세우는 과정 해가 있다고 가정 Fact(N) 은 N 팩토리얼 값을 반환해주는 함수라고 가정 합니다. 아직 Fact(N...

원문링크 : [알고리즘]동적계획법(DP)의 개념