구름톤 챌린지 3주차 학습 일기 - DP(동적 계획법)

 

DP, 다이나믹 프로그래밍, 동적 계획법 이라고 불리는 기법은 이전에 구했던 답을 재활용하는 방식이다. 

다시 말해, 이전에 구한 값을 저장해두고 다시 사용하므로써 불필요한 중복 계산을 최대한 줄이는 방법이다.(메모이제이션)

 

예를 들어서, 피보나치 수열을 재귀로 구현해보면 아래와 같다. 

 참고로 피보나치 수열은 처음 두개의 값이 0과 1이고, 이 다음 값은 맨 끝의 두 값을 더해서 만들어진다. 

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

function fibo(N){
  //첫 두값을 종단점으로 잡아줍니다.
  if (N === 0) return 0;
  if (N === 1) return 1;
  // N 번째 피보나치수는 N - 1번째, N - 2번째 피보나치수의 합이므로 재귀로 호출합니다.
  return fibo(N - 1) + fibo(N - 2);
}


console.log(fibo(8)); // 21
console.log(fibo(40)); // 102334155

이때, fibo(8)에 비해서 fibo(40)은 상대적으로 오랜 시간에 걸려서 출력이 된다. 왜냐하면 중복으로 호출되는 함수가 N이 커짐에 따라 빠르게 증가하기 때문이다. 

예를 들어서, fibo(4)를 호출하면, fibo(3)과 fibo(2)를 각각 호출하고, 

fibo(3)은 fibo(2)와 fibo(1)을 호출한다. 

이때, fibo(2)가 중복되는 것을 확인할 수 있고, N이 커질수록 중복으로 호출되는 횟수는 더욱 많아진다. 

 

이를 개선하기 위해 동적 프로그래밍을 사용하면 된다. 

N을 기준으로 0, 1 방향으로 내려가지 않고, 0, 1에서 N을 향해 올라가면 된다. 

const N = 40;
// 0번째 값이 0, 1번째 값이 1입니다. N에 대해 구하기 위해서는 N + 1칸의 배열을 선언해야합니다.
const fibo = new Array(N + 1).fill(0);
// 1번째 값을 1로 설정합니다.
fibo[1] = 1;

// 0, 1번째 값은 알고 있으므로 2번 값부터 N번 값까지 구하면 됩니다.
for (let i = 2; i <= N; i++) {
  fibo[i] = fibo[i - 1] + fibo[i - 2];
}

console.log(fibo[40]); // 102334155

 

참고자료

---

• 구름톤 프로젝트 매니징 자료