이번 포스팅으로 알아볼 내용은
알고리즘을 푸는 방법 중 하나인
DP ( 동적 계획법 : Dynamic Programming )
피보나치수열 ( Fibonacci )
메모이제이션( Memoization )
에 대해 알아보겠습니다.
수학과 컴퓨터 과학 그리고 경제학에서 동적 계획법( Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다.
동적 계획법은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용합니다.
동적 계획법의 이론은 주어진 문제를 풀기 위해 문제를 여러 개의 하위 문제(SubProblem)로 나누어 푼 다음, 그것을 경합하여 최종적인 목적에 도달하는 것입니다.
각 하위 문제의 해결을 계산한 뒤에 그 해결을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있습니다.
이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있습니다.
이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용합니다.
동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용됩니다.
동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고 그중에 최적의 풀이법을 찾아내기 때문입니다.
동적 계획법의 대표적인 예제로는 피보나치 수열이 있습니다.
피보나치 수열은 *재귀 함수를 사용하는 공식입니다.
피보나치수열의 기본 공식은 다음 예제 코드처럼 작성합니다.
예제 코드
public int fibo(int n){
if(n == 0){
return 0;
} else if(n == 1){
return 1;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}이 함수에서 fibo(5)를 구한다면 계산은 다음과 같이 이루어집니다.
- fibo(5)
- fibo(4) + fibo(3)
- (fibo(3) + fibo(2)) + (fibo(2) + fibo(1))
- ((fibo(2) + fibo(1)) + (fibo(1) + fibo(0))) + ((fibo(1) + fibo(0)) + fibo(1))
- (((fibo(1) + fib(0)) + fibo(1)) + (fibo(1) + fibo(0))) + ((fibo(1) + fibo(0)) + fibo(1))
여기에서 3번의 fibo(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어트립니다.
따라서 알고리즘의 시간 복잡도는 지수 함수가 됩니다.
중복된 계산식은 이미 값을 알고 있는 가정하에 값은 캐시( Cache )에 메모해놓습니다.
이는 배열에 저장하는 것으로 구현할 수 있습니다.
이를 메모이제이션( Memoization )이라고 합니다.
배열 변수에 값을 저장하는 예제입니다.
// 메모이제이션 배열 변수 memo 선언
int memo[1000];
public int fibo(int n){
if( n <= 1){
return n;
} else {
if( memo[n] > 0){
return memo[n];
}
memo[n] = fibo(n - 1) + fibo(n - 2);
return memo[n];
}
}
*재귀 함수란??
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법입니다.
재귀 호출이나 되부름이라고 부르기도 합니다.
재귀 호출의 입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 해당 재귀 함수는 무한히 반복되다가 콜스택 초과로 프로그램이 뻗어버립니다.
따라서 재귀함수 설계 시에는 입력값이 종료 조건을 수렴하는지를 꼭 검증해야 합니다.
( DP 방법에는 *Top-down 방식과 *Bottom-up 방식이 존재합니다. )
* Top-down : 큰 문제를 작은 문제로 쪼개면서 해결하고 재귀로 구현합니다.
* Bottom-up : 작은 문제부터 차례대로 해결, 반복문으로 구현합니다.
동적 계획법( Dyanmic Programming )을 통해서 문제를 풀이할 때는 메모이제이션을 위해 캐시 배열을 만들어
재귀 호출 혹은 반복문을 이용해 문제를 해결합니다.
이번 포스팅으로 DP와 피보나치수열의 재귀 호출 방식에 대해 알아보았습니다.