태그 · #tabulation

[멀티캠퍼스] 풀스택 개발자 아카데미 (16) - Algorithm(5)

동적 프로그래밍(DP)은 중복되는 부분 문제를 해결하고 최적 부분 구조를 활용하여 복잡한 문제를 효율적으로 푸는 알고리즘 설계 패러다임입니다. 이는 재귀와 캐싱을 활용하는 탑다운(메모이제이션) 방식과 반복문으로 테이블을 채워나가는 바텀업(타뷸레이션) 방식으로 나누어집니다. 이 두 접근법은 중간 계산 결과를 저장 및 재사용함으로써 불필요한 반복 계산을 방지하고 연산 성능을 획기적으로 향상시킵니다.