반응형 [알고리즘] 5. 동적 계획법 Index 1. 다이나믹 프로그래밍 2. 추천문제 3. 참고자료1. 다이나믹 프로그래밍Dynamic Programming- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음- 점화식 : 인접한 항들 사이의 관계식- Memoization: 한 번 계산한 결과를 메모리 공간에 메모하는 기법(=Caching), - Top-down(메모이제이션) 방식과 Bottom-up 방식이 존재- Bottom-up 방식을 사용시 결과 저장용 리스트는 DP 테이블 이용- 분할 정복은 부분 문제의 중복이 없음 (조건)1) Optimal Substructure(최적 부분 구조)- 큰 문제를 작은 문제로 나눌 수 있으며 작은.. 2023. 10. 5. 이전 1 다음 반응형
