12장 동적 프로그래밍

• 11장에서는 재귀적으로 작성하는 법과 재귀로 보다 복잡한 문제를 해결하는 법을 배웠다.
• 그러나 재귀로 어떤 문제를 해결할 수는 있어도 제대로 사용하지 않으면 또 다른 문제가 발생하기도 한다.
• 재귀를 잘못 사용할 경우 알고리즘의 시간 복잡도가 O(2^N)과 같은 가장 느린 빅 오 카테고리에 속하게 될 수 있다.
• 12장에서는 재귀의 속도를 느리게 만드는 가장 흔한 걸림돌을 찾고 그러한 알고리즘을 빅 오 관점에서 어떻게 나타내는지, 어떻게 개선하는지를 배운다.

1. 불필요한 재귀 호출

• 동일한 하위 문제의 계산 결과를 여러 번 호출하는데, 동일한 인자를 넣었을 때 항상 동일한 결과가 나올 때

2. 빅 오를 위한 작은 개선

• 이러한 추가적인 재귀 호출을 전부 없앨 수 있는 방법이 있다.
• 코드에서 결과를 변수에 저장하면 된다.
• 비결은 필요한 함수 호출을 한 번만 수행하고 그 결과를 변수에 저장함으로써 함수를 다시 호출하지 않아도 되게 하는 것이다.

3. 재귀의 효율성

• 빅 오는 데이터 원소가 N개일 때 얼마나 많은 단계 수가 필요한가라는 핵심 질문에 대한 답이었다.
• 불필요한 재귀 호출을 피하는 것이 재귀를 빠르게 만드는 핵심 비결이다.
• 계산 결과를 변수에 저장하는 부분이 언뜻 봐서는 코드에서 아주 사소한 변화더라도 궁극적으로 함수 속도를 O(2^N)에서 O(N)으로 변화시킨다.

4. 하위 문제 중첩

• 피보나치 수열
• 하위 문제: 동일한 문제를 작게 만들어 해결할 때, “작은 문제”를 하위 문제라고 부른다.
• 하위 문제가 중첩되는 이유는 fib(n - 2)와 fib(n - 1)이 결과적으로 동일한 함수를 여러번 중복해서 호출하기 때문이다.
• 결국 알고리즘은 O(2^N)의 속도로 매우 느리게 호출된다.

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

• 동적 프로그래밍(dynamic programming)은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다.
• 일반적으로 두 가지 기법이 있다.

1. 메모이제이션(memoization)
   • 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다.
2. 상향식을 통한 동적 프로그래밍

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

• 이 기법은 훨씬 덜 세련되고 심지어 기법이라고 부르기도 애매하다.
• 상향식이 동적 프로그래밍의 하나로 간주되는 이유는 동적 프로그래밍이 재귀적으로 풀 수 있는 문제에 대해 중첩되는 하위 문제를 중복 호출하지 않게 해주기 때문이다.
• 재귀 대신 루프를 사용하는 것도 이렇게 하는 방법 중 하나다.

6.2 메모이제이션 대 상향식

• 메모이제이션을 쓰더라도 재귀가 반복에 비해 오버헤드가 더 든다는 사실을 간과해서는 안 된다.
• 구체적으로 말하면, 재귀를 어떻게 사용하든 컴퓨터는 호출 스택에 모든 호출을 기록해야 하므로 메모리를 소모한다.
• 메모이제이션 자체도 해시 테이블(혹은 배열)을 사용하므로 마찬가지로 메모리 공간을 추가로 소모한다.
• 재귀가 매우 직관적이지 않은 이상 일반적으로 상향식을 택하는 편이 더 낫다.
• 재귀가 더 직관적이면 재귀를 사용하되 메모이제이션으로 빠르게 만들어야 한다.