분할 정복을 적용하는데 있어서 주의할 점
분할 정복이 부적절한 경우
- 입력이 분할될 때 마다 분할된 부분 문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 커지는 경우
- ex) 피보나치 수 구하기
- recursive하게 정의 : F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
- 예를 들어, n 번째의 피보나치 수를 구하는데 F(n) = F(n-1) + F(n-2)로 정의되므로 재귀 호출을 사용하는 것이 자연스러워 보이나, 이 경우의 입력은 1개이지만, 사실상 n의 값 자체가 입력 크기인 것이다
- 따라서 n이라는 숫자로 인해 2개의 부분 문제인 F(n-1)과 F(n-2)가 만들어지고, 2개의 입력 크기의 합이 (n-1) + (n-2) = (2n-3)이 되어서, 분할 후 입력 크기가 거의 2배로 늘어난다
- 이 경우 시간 복잡도는 O(2^n)
Fibonacci Number를 구하기 위한 효율적인 알고리즘
FibNumber(n)
1. F[0]=0
2. F[1]=1
3. for i=2 to n
4. F[i] = F[i-1]+ F[i-2]
- 중간 결과를 배열 F에 저장해 두고, 이를 이용한다.
- 시간복잡도: 𝑂(𝑛)
- 위와 같이 중간 결과를 table(배열)에 저장해 이를 이용해 보다 큰 크기의 instance에 대한 solution을 구하는 방법을 dynamic programming 이라고 부른다.
- 피보나치 예시에서는 DP에서 중간 결과를 저장해두는 메모이제이션을 사용하였다.