목록2025/05/05 (1)
kimgusxo 님의 블로그
다이나믹 프로그래밍(Dynamic Programming)
1. DP(Dynamic Programming)이란?- 다이나믹 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하고 그 결과를 중복해서 다시 계산하지 않도록 저장하거나 차례차례 결과를 쌓아올리는 기법이다.- 분할정복과 비슷하지만 하위 문제가 중복되어 등장할 때 중복 계산을 제거하는것이 차이점이다. 1-1. 핵심 아이디어- 중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 등장하면 한 번 계산한 값을 저장해놨다가 재사용- 최적 부분 구조(Optimal Substructure): 문제의 최적 해가 하위 문제의 최적해들로 만들어져야 함 1-2. 장단점- 장점: 중복 계산을 제거하여 시간복잡도가 감소, 단계별 구현 패턴이 일정- 단점: 상태 저장용 메모리(배..
Algorithm
2025. 5. 5. 21:17