동적계획법 예시 피보나치수열
피보나치 수열이란
- 1 + 1 + 2 + 3 + 5 + 8 + 13 ... 식과 같이 1 + 1부터 시작해서 더해서 나온 결과와 그 앞에 있는 숫자를 계속해서 더해가는 식을 피보나치 수열이라 한다.
Memoization기법을 사용하지 않은 수열
function fibo(num) {
if(num <= 1) return num;
return fibo(num - 2) + fibo(num - 1)
}위의 코드는 매우 간단하게 피보나치 수열을 풀 수 있지만 간단히 10번째 수열을 구하려고 해도 아래의 디버깅 홈페이지에서 봐도 수 많은 연산이 필요하게 된다.
하지만 동적계획법의 핵심인 memoization 기법을 사용하게 된다면 어떻게 될까?
동적계획법의 알고리즘
- 문제를 부분 문제로 나눈다.
- 가장 작은 문제의 해를 구한 뒤에 테이블에 저장
- 테이블에 저장되어있는 데이터를 사용해 그 문제의 결과가 필요하다면 다시 계산을 하는 것이 아닌 저장되어있는 답을 가져와서 전체의 문제의 답을 구한다.
function fibo_memo(num){
let newArr = [0, 1];
let fi = (num) => { // 저장된 결과값이 있는지 없는지 판별해주는 함수를 선언
if(newArr[num] !== undefined){ // 만약 결과값이 있다면 바로 리턴
return newArr[num];
}
// 없다면 결과 배열에 결과값을 추가
newArr[num] = fi(num - 1) + fi(num - 2);
return newArr[num];
};
return fi(num);
}위와 같이 결과값을 따로 저장해주는 배열을 선언하고 그 안에 결과가 들어있는지 아닌지를 판별해 있다면 그대로 가져다 쓰고 없다면 새롭게 추가 해주며 정답을 찾아간다면 그전에 답을 구할때까지 계속해서 재귀하여 푸는 방식보다 훨신 적은 연산으로 답에 도달할 수 있다.
위와 아래의 사진에서 아래쪽 step을 본다면 확연한 차이를 느낄수가 있다.
