재귀와 동적 프로그래밍

재귀적 해법의 접근법

재귀적 해법은 부분문제에 대한 해법을 통해 완성된다. 가장 흔하게 사용되는 방법은 상향식(botton-up), 하향식(top-down), 반반(half-half)이 있다.

1. 상향식 접근법

하나 풀고 그걸로 다음 거 풀고 다음 거 풀고..
이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다. 가장 직관적인 방법

2. 하향식 접근법

한 번 나누고 또 나누고 ... 풀고
풀기 전에 부분문제로 나눈 다음 문제를 해결한다.

3. 반반 접근법

데이터를 반으로 나눠 해결한다. 이진 탐색에서 특별한 원소를 찾을 떄, 왼쪽 절반과 오른쪽 절반을 보는 것처럼.

재귀적 해법 vs 순환적 해법

재귀적 알고리즘은 스택에 계속 함수를 쌓기 때문에, 공간 복잡도가 높아진다. 따라서, 재귀적 알고리즘을 순환적 알고리즘으로 바꾸는 것이 나을 수 있다. 하지만 순환적 알고리즘이 더 어렵다.

동적계획법 & 메모이제이션

중복해 나타나는 값을 캐시에 저장하고 이를 사용하는 방법을 메모이제이션이라 한다. 하향식 동적 프로그래밍을 메모이제이션으로, 상향식 접근법을 동적 프로그래밍으로 구분하기도 한다. 하지만 이 책에서는 둘 다 동적 프로그래밍이라 부른다.

피보나치 수열

재귀

		int fibonicci(int i) {
          if (i == 0) {
            return 0;
          }
          if (i == 1) {
          	return 1;
          }
          return fibonacci(i-1) + fibonacci(i+1);
        }

이 함수의 수행 시간은 O(2^n)이다. 따라서 노드의 크기가 커질수록 실행 시간은 기하급수적으로 증가하기 때문에, 최적화가 필요하다.

메모이제이션

위의 재귀적 접근법은 많은 노드가 중복되기 때문에, 이 값을 캐시에 넣고 재사용하는 것(메모이제이션)이 유리하다. 위의 코드를 메모이제이션으로 구현하면 다음과 같다.

		int fibonacci(int n) {
          return fibonacci(n, new int[n + 1]); // ???
        }
        
        int fibonacci(int i, int[memo]) {
          if(i == 0 || i == 1) {
          	return i;
          }
          if(memo[i] == 0) {
          	memo[i] = fibonacci(i-1, memo) + fibonacci(i-2, memo);
          }
          return memo;
        }

일반적인 컴퓨터에서 재귀 코드를 돌려보면 50 번째 수를 찾는 데 1분 이상 소요된다. 하지만 동적 프로그래밍을 사용하면 10000 번쨰 수를 찾는 데도 몇 ms 밖에 소요되지 않는다.
즉, 동적 프로그래밍을 사용할 수 있다면, 사용할 방법을 찾는 것이 좋다.

상향식 동적 프로그래밍

먼저 초기 사례인 fibonacci(1)과 fibonacci(0)을 계산한다. 이 후, 그 둘을 사용해 2,3,4,...을 계산해나간다.

		int fibonacci(int n) {
          if(n == 0) {
            return 0;
          } else if(n == 1) {
          	return 1;
          }
          int[] memo = new int[n];
          memo[0] = 0;
          memo[1] = 1;
          for(int i=0; i<n; i++) {
            memo[i] = meme[i-1] + memo[i-2];
          }
          return memo[n-1] + memo[n-2];
        }

memo[i]는 memo[i+1]과 memo[i+2]를 계산할 때 빼고 전혀 사용하지 않는다. 다음과 같이 더 간단하게 표현할 수 있다.

		int fibonacci(int n) {
          if(n == 0) {
          	return 0;
          }
          int a = 0;
          int b = 1;
          for(int i=2; i<n; i++) {
          	int c = a + b;
            a = b;
            b = c;
          }
          return a + b;
        }

thanks, bean