12장 동적 프로그래밍

재귀는 제대로 사용하지 않으면 O(2ⁿ)같은 가장 느린 빅 오 카테고리의 주된 요인이 된다.

12.1 불필요한 재귀 호출

다음의 재귀 함수는 배열의 최댓값을 찾는다.

function max(array) {
  if (array.length === 1) return array[0];

  if (array[0] > max(array.slice(1))) {
    return array[0];
  } else {
    return max(array.slice(1));
  }
}

만일 배열의 요소가 한 개뿐이라면 그 값이 최댓값이다.

각 재귀 호출의 핵심은 하나의 수(array[0])와 나머지 배열의 최댓값 간의 비교다.

if - else 조건을 보면, 조건문 앞 뒤로 max() 함수가 두 번 나온다. 이는 비효율적이다.

[1, 2, 3, 4]를 예시로 들면, 1과 [2, 3, 4]의 최댓값을 비교한다. 이어서 2와 [3, 4]의 최댓값을 비교한다. 이어서 3과 [4]를 비교하고, [4]의 최댓값을 찾는 것이 기저 조건이다.

코드가 어떻게 실행되는지 제대로 알려면 바닥 호출부터 분석해 호출 사슬을 따라 올라가야 한다.

12.1.1 max 재귀 분석

max([4])를 호출하면 기저 조건이므로 4를 반환한다.

호출 사슬 위로 올라가서 max([3, 4])를 호출하면, 배열의 요소가 1개가 아니므로 3과 max([4])를 비교하면서 max([4])를 호출한다.

3은 4보다 크지 않으므로 else문인 max(array.slice(1))을 실행하고, max([4])가 반환되며 두 번째로 호출된다.

즉, max([3, 4])는 max([4])를 두 번 호출한다.

max([2, 3, 4])는 2와 max([3, 4])를 호출하고, max([3, 4])는 앞서 봤던 것처럼 max([4])를 두 번 호출한다. 그리고 else문에 따라 max([3, 4])를 호출하고, max([4])는 추가로 두 번 더 호출된다.

max([1, 2, 3, 4])를 호출하면 실제로 max함수를 총 15번 호출하게 된다. 이때 모든 15번의 호출이 필요한 것은 아니다. max([4])는 한 번만 호출되면 충분한데도 8번이나 호출되고 있다.

12.2 빅 오를 위한 작은 개선

추가적인 재귀 호출을 전부 없애기 위해서, 코드에서 max를 딱 한 번만 호출하고 그 결과를 변수에 저장하는 방법을 쓴다.

function max(array) {
  if (array.length === 1) return array[0];

  let maxOfRemainder = max(array.slice(1));

  if (array[0] > maxOfRemainder) {
    return array[0];
  } else {
    return maxOfRemainder;
  }
}

이렇게 수정하면 max([1, 2, 3, 4])는 max를 4번만 호출한다. 필요한 함수 호출을 한 번만 수행하고 그 결과를 변수에 저장함으로써 함수를 다시 호출하지 않아도 되게 하는 것이 비결이다.

12.3 재귀의 효율성

12.2의 max 함수는 배열 내 값 개수만큼 스스로를 호출한다. 즉 O(N)이다.

하지만 12.1의 개선되지 않은 max 함수는 데이터가 1씩 커질 때 필요한 단계수가 대략 2배씩 늘어나므로 O(2ⁿ) 패턴이다. 현저히 느린 알고리즘이다.

불필요한 재귀 호출을 피하는 것이 재귀를 빠르게 만드는 핵심이다.

12.4 하위 문제 중첩

피보나치 수열의 N번째 수를 반환하는 함수를 구현한다.

function fib(n) {
  if (n === 0 || n === 1) {
    return n;
  }

  return fib(n - 2) + fib(n - 1);
}

매우 간결하지만 함수가 자기 자신을 두 번 호출한다. 자신을 두 번 호출하는 함수는 O(2ⁿ)이 되기 쉽고, 실제로 이 함수는 O(2ⁿ)이다.

이 함수는 변수에 저장할 데이터가 fib(n - 2), fib(n - 1)로 두 개이다. 둘 중 하나만 저장해서는 나머지 하나를 얻지 못한다.
이런 것을 하위 문제 중첩이라고 부른다.

피보나치 수열의 하위 문제는 더 작은 수를 먼저 계산하는 것이다. 피보나치 문제의 하위 문제가 중첩되는 이유는 fib(n - 2), fib(n - 1)이 같은 함수를 여러번 호출하기 때문이다. 가령, fib(4), fib(5)는 둘 다 fib(3)을 호출한다.

12.5 메모이제이션을 통한 동적 프로그래밍

동적 프로그래밍은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다.

동적 프로그래밍을 통한 알고리즘 최적화에는 두 기법 중 하나를 선택한다: 1) 메모이제이션, 2) 상향식.

메모이제이션은 하위 문제가 중첩될 때 재귀 호출을 감소시키는 기법이다. 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다.

피보나치 예제에서 fib(3)을 호출하면 함수는 계산을 하고 2를 반환한다. 단, 반환하기 전 함수는 결과를 해시 테이블에 저장한다. {3 => 2}. 이는 fib(3)의 결과가 2라는 뜻이다.

같은 방식으로 새로 계산한 결과를 모두 메모이징할 수 있다. { 3 => 2, 4 => 3, 5 => 5, 6 => 8 }... 이런 해시 테이블로 다음 재귀 호출을 피할 수 있다.

만일 fib(4)를 실행한다면, fib(3)을 호출하기 전 해시 테이블에 키를 3으로 하는 값이 있는지 확인하고, 없을 때에만 fib(3)을 호출하면 된다.

메모이제이션을 사용하면 새로운 계산을 할 때마다 해시 테이블에 저장하고 다음 계산에 활용할 수 있다. 하지 않았던 계산만 수행하면 된다.

12.5.1 메모이제이션 구현

function fib(n, memo = new Map()) {
  if (n === 0 || n === 1) {
    return n;
  }

  if (!memo.get(n)) {
    memo.set(n, fib(n - 2, memo) + fib(n - 1, memo));
  }

  return memo.get(n);
}

각 재귀 함수가 해시 테이블에 접근하게 하기 위해 함수의 두 번째 인자(memo)의 기본값으로 빈 해시 테이블을 전달한다.

재귀 호출을 하기 전 if (!memo.get(n)) 조건을 통해 fib(n)이 이미 계산됐는지 확인하고, 계산되지 않았을 때만 계산을 진행한다. 계산을 진행하면 해시 테이블 키 n에 값을 저장하므로 다시 계산할 필요가 없다.

이 함수는 2N-1번 호출되므로, O(N)이다. O(2ⁿ)에 비해 엄청난 향상이다.

12.6 상향식을 통한 동적 프로그래밍

상향식은 같은 문제를 재귀 대신 반복문과 같은, 다른 방식으로 해결한다는 뜻이다.

상향식이 동적 프로그래밍의 하나로 간주되는 이유는, 동적 프로그래밍이 중첩되는 하위 문제를 중복 호출하지 않게 해주기 때문이다. 반복문을 사용하는 것도 이렇게 하는 방법 중 하나다.

12.6.1 상향식 피보나치

function fib(n) {
  if (n === 0) return 0;

  let a = 0;
  let b = 1;

  for (let i = 1; i < n; i++) {
    let temp = a;
    a = b;
    b = temp + a;
  }

  return b;
}

처음 두 수인 0과 1을 각각 a, b에 담는다. 이어서 1부터 n까지 반복문을 돌며 계산을 진행한다. 1부터 N까지의 반복문이므로 O(N)이다.

12.6.2. 메모이제이션 대 상향식

메모이제이션을 쓰더라도 재귀가 반복문에 비해 오버헤드가 더 든다는 사실을 간과해서는 안 된다.

재귀를 어떻게 사용하든 컴퓨터는 호출 스택에 모든 호출을 기록해야 하므로 메모리를 소모한다. 메모이제이션 자체도 해시 테이블을 사용하므로 추가로 컴퓨터 공간을 소모한다.

재귀가 매우 직관적이지 않은 이상 상향식을 택하는 편이 더 낫다. 재귀가 더 직관적이라면 재귀를 사용하되 메모이제이션을 사용해야한다.

12.7 마무리

효율적인 재귀 코드를 작성하는 능력을 갖추게 됐다!