동적계획법과 피보나치 수열

패스트캠퍼스 코딩테스트 강좌의 잔재미코딩 님 부분을 참고하였습니다.

동적 계획법 (Dynamic Programming)과 분할 정복(Divide and Conquer)

동적 계획법

• 통상 DP라고 많이 부른다.
• 상향식 접근법으로 가장 최하위 해답을 구한 뒤 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 문제의 해를 활용하여 보다 큰 크기의 부분 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘
• 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용된다.
  • 예) 피보나치 수열
• Memoization 기법을 사용한다.
  • 프로그램 실행 시 이전에 계산한 값을 저장하고 재활용하여 전체 실행 속도를 빠르게 하는 기술

분할 정복

• 문제를 나눌 수 없을 때까지 나누어 각각을 풀고 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
  • 일반적으로 재귀함수로 구현된다.
• 문제를 잘게 쪼갤 때 부분 문제들은 서로 중복되지 않는다.
  • 병합 정렬, 퀵 정렬 등

공통점과 차이점

1. 공통점
   • 문제를 잘게 쪼개서 가장 작은 단위로 분할한다.
2. 차이점
   • 동적계획법
     • 부분 문제는 중복되어 상위 문제 해결 시 재활용된다.
     • Memoization 기법이 사용된다.
   • 분할 정복
     • 부분 문제는 서로 중복되지 않는다.
     • Memoization 기법을 사용하지 않는다.

동적계획법으로 구현한 피보나치 수열

// n번째 요소의 값을 반환하는 피보나치 수열
const fibo = n => {
  // 빈 배열 생성
  let cache = [];
  // 규칙성이 없는 항목 처리
  cache[0] = 0;
  cache[1] = 1;
  // 2번째 요소부터 피보나치 적용
  for (let i = 2; i < n + 1; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }
  return cache[n];
};

console.log(fibo(7));