-
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번째 항의 피보나치 수열을 구한다고 하자.
전체적인 수행을 나타내 보자면,
Fibo 4=Fibo 3+Fibo 2
Fibo 3=Fibo 2+Fibo 1
Fibo 2=Fibo 1+Fibo 0(0)
Fibo 2=Fibo 1+Fibo 0(0)
이러한 동등한 항의 계산이 있을 경우
계산량이 기하급수적으로 증가하니,
이러한 항을 배열에 저장한다면
더 이상 함수 호출로 기저사례에 도달하지 않아도
원하는 답을 더욱 빠른 시간내에 도출 할 수 있다.
이런 저장을 메모이제이션이라고 하고,
이 경우 O(N)만에 구할 수 있다.
3. 여담
행렬을 이용시 O(log N)만에 피보나치 수열의 값을 구할 수 있다.