[알고리즘] 동적 계획법(Dynamic Programming)
동적 계획법이란? - 문제를 가장 작은 단위로 분할 > 부분 문제의 해를 활용 해 보다 큰 부분 문제를 해결 > 최종적으로 전체 문제를 해결하는 알고리즘 - 분할 정복과 비슷하게 문제를 잘게 나누어 접근하나 분할정복과는 성능차이가 있다. - Memoization (메모이제이션) 기법을 사용 더보기 프로그램 실행 시 이전에 계산한 값을 저장 및 재사용 함으로써 재 계산을 방지하고 전체 실행속도를 빠르게 하는 기술 - 부분 문제는 해결 후 상위 문제 해결 시 재 활용됨 분할 정복과의 차이점 분할정복 동적 계획법 분할한 문제가 반복되지 않음 분할한 문제가 반복되어 재활용 가능 조합 폭발(Combinatorial explosion)이 발생할 확률이 있다. 조합 폭발(Combinatorial explosion)이..
Algorithm
2020. 11. 1. 01:08