피보나치 수열1 [알고리즘] 다이나믹 프로그래밍 (동적 계획법) 동적 계획법 Dynamic Programming (DP) 동적 계획법은 주어진 문제를 하위 문제로 나눠 풀고 그 결과를 저장해 다음 문제를 푸는데 사용하는 알고리즘이다. 이는 분할 정복 Divide and Conquer과 비슷해보이지만 동적계획법에서는 하위문제가 서로 종속성을 가진다는 점이 다르다. 즉 문제를 풀고 그 답이 다른 문제에 영향을 끼칠 수 있다는 것이다. (= 메모이제이션) 동적 계획법의 핵심은 같은 문제의 중복 호출을 피하자는 것이다. 동빈나님의 설명으로는 '하나의 문제를 단 한번만 풀도록 하는 알고리즘' 이라는 것이다. 동적계획법을 사용하기 적절한 문제의 특징은 이렇다. 최적화 문제이다 재귀적 구조를 가져 재귀 구현했을 때 중복 호출로 비효율이 발생한다. 최적화 문제라는 것은 하나의 문제.. 2021. 9. 9. 이전 1 다음
