알고리즘/동적 계획법
-
Dynamic Programming(동적 계획법)알고리즘/동적 계획법 2022. 9. 6. 22:45
도입 오늘은 동적계획법(DP)에 대해 소개 해보겠다. 먼저 필자는 아직도 동적 계획법을 잘 못한다. Dynamic Programming이라는 어려운 이름에 ㅎㄷㄷ 할 수 있지만, 당시 연구실에서 연구비 많이 받을려고, 이런 이름으로 지었다고 한다. 1. 동적계획법 정의 먼저 동적계획법은 어떠한 문제를 다른 부분 문제로 나누는 것을 의미한다. 예를 들어 대표적인 예는 피보나치 수열이다. Fibo n = Fibo n-1 + Fibo n-2 로 나타낼 수 있다. Fibo n이라는 문제를 부분적으로 나눈 것이다. 이 경우에 n부터 시작해 함수 호출이 약 2배씩 증가함으로 총 O(2^N)에 근사하는 시간복잡도를 가지지만, 메모이제이션이라는 기법을 사용하면 간단해진다. 2. 메모이제이션 우리는 4번째 항의 피보나치..