[Algorithms] 동적 계획법(Dynamic Programming) 설명

• 동적 계획법이란 - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다
• 동적 계획법을 적용하려면 다음 두 가지 속성을 만족시켜야 하는데,
  1. 부분 반복 문제 (Overlapping Subproblem) - 대표적으로 피보나치 수열의 경우 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가지고 있다. 
     • 문제: n 번째 피보나치 수 구하기 | 부분문제: n-1번째 + n-2번째 피보나치 수 구하기
     • 문제: n-1번째 피보나치 수 구하기 | 부분문제: n-2번째 + n-3번째 피보나치 수 구하기
  2. 최적 부분 구조 (Optimal Substructure) - 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것. 피보나지 수열에서 fib(n) = fib(n-1) + fib(n-2) => fib(n)이 최적의 답이 되려면 작은 부분 문제인 fib(n-1)과 fib(n-2)가 최적의 답이어야 한다
  3.  

 

• 최적 부분 구조를 만족한다면, 어떤 한 문제의 답은 일정하게 나온다. 예를들어 fib(3) 의 경우, 이 값이 어느 곳에 위치하든 모두 같은 fib(3) 값을 가지게 될 것이다. 
• 이 때 필요한 것이 Memoization 메모이제이션 이다. Memoization이란 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 

• 동적 계획법은 2가지 방식으로 해결 할 수 있는데

1. Top-Down - 위에서 아래로 접근, 큰 문제에서 부분 문제로 쪼개가며 재귀 호출을 이용해 푸는 방법

2. Bottom-Up - 아래에서 위로, 부분 문제를 풀어가며 점차 큰 문제를 푸는 방법. for 문을 이용해 푸는 방법이 이에 해당