동적계획법1

• 

  210705 동적 계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming, DP) vs 분할 정복법(Divide and Conquer) 문제를 분할하여 작은 문제로 만들어 해결한 후 합쳐서 문제 해결하는 것은 동일 동적 계획법은 서브 문제들 간의 관계가 존재하여 overlapping (작은 문제들이 중복되는 일) 발생 => 작은 문제들의 결과 저장하여 다시 계산하는 일 생략 서브 문제들간의 overlapping 없음 최적 부분구조(Optimal Substructure) 전체 문제가 최적(optimal)구조가 되려면 그 서브 문제들도 최적화 된 솔루션으로 해결가능 해야 함. => 문제를 해결할 때 서브 문제들을 해결하여 그 결과들을 이용하여 최종적인 답 구함 이러한 구조를 가진 문제로 대표적인 예가 최단 경로 문제 피보나치 210.. 미가공 필기(알고리즘) 2021. 7. 6.