🦊 11. Recursion & Dynamic programming

11. Recursion & Dynamic programming

접근법

재귀적 해법은, 부분문제에 대한 해법을 통해 완성된다.

상향식 접근법 (Bottom-up)

상향식 접근법은 가장 직관적인 경우가 많다.

이 접근법은 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작해

이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다.

하향식 접근법 (Top-down)

어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있는지 생각해봐야 한다.

나뉜 부분문제의 경우 서로 겹치지 않도록 주의한다.

반반 접근법

데이터를 절반으로 나누는 방법이다.

이진 탐색과 병합 정렬은 이런 접근법을 이용한다.

재귀적 해법 vs. 순환적 해법

재귀적 알고리즘은 공간 효율성이 나빠질 수 있다.

재귀 호출이 한 번 발생할 때마다 스택에 새로운 층이 추가되고

재귀의 깊이가 n 일때 O(n) 만큼의 메모리를 사용하게 된다.

따라서 재귀적 알고리즘을 순환적으로 구현하는 것이 더 나을 수도 있다.

모든 재귀적 알고리즘은 순환적으로 구현될 수 있지만, 때로는 더 복잡하다.

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

동적 프로그래밍은 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 부분 문제를 찾아내는 것이 관건이다.

이를 찾은 뒤에 나중을 위해 현재 결과를 캐시에 저장해두면 된다.

동적 프로그래밍을 설명하는 가장 간단한 예시는 n번째 피보나치 수를 찾는 것이다.

피보나치 수열

• 재귀

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

각 재귀호출에 소요되는 시간은 O(1) 이고 트리에 있는 노드의 개수는 대략 O(2^n) 개이다.

따라서 수행 시간은 약 O(2^n) 정도가 된다.

• 하향식 동적 프로그래밍(메모이제이션)

재귀 트리를 그려보면 많은 노드들이 중복되어 호출된다.

매번 fib(i) 를 계산할 때마다 이 결과를 캐시하고 저장된 값을 사용하는 것이 메모이제이션이다.

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[i];
}

• 상향식 동적 프로그래밍

구현을 상향식으로 할 수도 있다.

재귀적인 메모이제이션으로 접근하되, 그걸 뒤집는다고 생각해보자.

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 = 2; i < n; i++) {
		memo[i] = memo[i - 1] + memo[i - 2];
	}
	return memo[n - 1] + memo[n - 2];
}

memo[i] 는 memo[i+1] 과 memo[i + 2] 를 계산할 때만 사용되고 그 뒤에는 사용되지 않는다.

따라서 변수 몇 개를 사용해서 풀 수도 있다.