recursion1 [Algorithm] Dynamic Programming vs. Recursion 동적계획법(Dynamic programming)은 재귀구조(Recursion)와 비교해서 살펴봐야하는 방법론인데요, 사실 두 용어가 무 자르듯 딱 상호베타적으로 구분되는 것은 아닌데 좁은 의미로 사용될 때 두 가지가 어떤 차이가 있는지 살펴보겠습니다. 두 방법론 모두 부분문제의 해결책을 전체 문제의 해결책으로 활용한다는 점에서는 공통점이 있습니다. 하지만 재귀구조는 주로 Top-Down 방식으로 (특히 함수를 재귀적으로 호출하는 방식으로) 적용하는 반면 동적계획법은 Bottom-up 방식을 사용하거나 Top-Down + Memoization 결합방식을 차용합니다. 재귀구조는 같은 작업을 여러번 반복하게 될 가능성이 있어서 깊은 재귀구조에서는 stack-overflow에러가 발생할 위험이 있습니다. 피보.. 2025. 2. 19. 이전 1 다음 반응형
