배움 __IL/자료구조&알고리즘

알고리즘 3줄 정리 [DP : Memoization, ]

Mo_bi!e 2023. 12. 28. 09:00

Dynamic Programming

- Memoization 정리

  • 핵심개념
    • 피보나치 수열의 동적 프로그래밍과 메모이제이션 방식의 핵심은 중복 계산을 방지하기 위해 캐시를 사용하여 이미 계산된 값을 저장하고 재사용함으로써, 재귀 호출의 효율성을 높이고 시간 복잡도를 지수적인 O(2^n) 에서 선형적인 O(n)으로 줄이는 데에 있습니다.
    • 기저 사례를 적절히 처리하여 재귀 호출의 종료 조건을 제공하며, 이를 통해 계산 속도를 크게 향상시킵니다.