분할 정복 주의할점

앞에서 합병정렬, 퀵정렬, 최근접 점 찾기 알고리즘을 분할 정복 알고리즘 개념을 사용해서 구현해보았습니다. 

오늘은 분할 정복의 주의할 점에 대해서 설명해보겠습니다. 

 

1. 분할 정복이 분리한 경우

분할된 부분 문제의 입력 크기의 합 > 분할되기 전의 입력크기보다 매우 커지는 경우

 

2. 예시

=> 피보나치 수열을 다음과 같이 재귀 함수를 구현한 경우

function fibonacci(n) {
  if (n <= 1) return n;
  
  // F(n) 문제를 F(n-1)과 F(n-2) 문제로 분할
  return fibonacci(n - 1) + fibonacci(n - 2); 
}

 

분할된 부분 문제의 입력 크기의 합 : (n-1) + (n-2) = 2n - 3 

분할되기 전의 입력크기 : n

 

=> 2n - 3은 원래 문제 크기 n보다 거의 두 배나 큽니다. 🚨

 

 

3. 분할된 부분 문제의 입력 크기의 합 이 커진다는 의미는? 

=> " 연산 중복을 하고 있다 "

ex) fibonacci(5)를 호출하면,

1. fib(5)는 fib(4)와 fib(3)을 호출합니다

2. fib(4)는 fib(3)과 fib(2)를 호출

3. fib(3)은 fib(2)와 fib(1)을 호출

4. fib(3)은 다시 fib(2)와 fib(1)을 호출

...(생략)

=> 이렇게 적다보면, fib(3)이 벌써 여러번 호출 되었습니다. 이런식으로 중복 호출되어, 시간 복잡도가 O(2^n)이라는 최악의 성능을 보이게 됩니다. 

=> 심하게 겹칠 때(Overlapping Subproblems), 분할 정복은 재앙이 됩니다. 

 

 

4. 이를 해결하려면

 이런 문제는 보통 동적 계획법(Dynamic Programming)이나 메모이제이션(Memoization)을 사용해 중복 계산을 피하는 방식으로 풀어야 합니다.

 

그래서 피보나치 수열을 조금이라도 개선한다면,

// 메모를 위한 저장 공간
const memo = {};

function fibonacci(n) {
  // 만약 메모에 이미 값이 있으면, 바로 그 값을 반환
  if (n in memo) return memo[n]; 
  if (n <= 1) return n;

  // 계산한 결과를 메모에 저장하고 반환
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return memo[n];
}

이렇게 되면, 중복된 연산을 줄임으로서 n만큼 수행하여 O(n)의 시간복잡도를 가지게 됩니다