동적 계획법(dynamic programming) feat. 피보나치 수열

분할한 문제의 답을 기억해 두고, 이를 재사용함으로써 같은 문제를 여러 번 푸는 낭비를 방지한다는 프로그래밍 기법

상향식 접근방법

 

🟩 특징

각 소문제는 원래 주어진 문제와 동일한 문제 👉 입력 크기만 작아진 문제

소문제들은 서로 독립일 필요없다.

해를  구축하는데 테이블을 사용한다.

 

최솟값/최댓값을 구하는 최적화 문제에 주로 사용

"최적성의 원리"를 반드시 만족하는 문제에만 적용 가능하다.

주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다.

 

🟩 처리 과정

1. 최적성의 원리가 주어진 문제에 성립하는 지  확인

2. 주어진 문제에 대해서 최적해를 제공한느 점화식 도출

3. 가장 작은 소문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장

4. 테이블에 저장된 소문제의 해를 이용하여 점차적으로 입력의 크기가 큰 상위 문제의 해를 구해 나감

 

🌟 피보나치 수열 (분할 정복 방법)

앞의 두 수 더한 값이 이후의 값

#include <stdio.h>

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

int main(void) {
	int n;
	for (n = 0; n < 8; ++n) {
		printf("%d, ", fibonacci(n));
	}
	printf("\n");

	return 0;
}

 

문제점 : 같은 인수이면 반환값도 동일하므로 여러 번 같은 인수로 피보나치 함수를 호출하는 것은 낭비

👉 동적 계획법으로 해결 가능

 

🌟 피보나치 수열 (동적 계획법)

#include <stdio.h>
#define LENGTH 100

int fibonacciNumbers[LENGTH];

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

	return fibonacciNumbers[n];
}

int main(void) {
	for (int n = 0; n <= 8; ++n) {
		printf("%d, ", fibonacci(n));
	}
	printf("\n");

	return 0;
}

 

재귀호출과 동적 계획법을 함께 사용하면 더욱 효율적인 처리를 만들 수 있다.

초기화 처리 함수 추가. 피보나치 수를 기억하는 배열의 요솟값을 모두 -1로 초기화한다. -1은 피보나치 수가 구해지지 않았음을 나타낸다. -1로 한 이유는 피보나치 수는 0 이상의 값이기 때문이다. 

동적 계획법으로 재귀 호출의 낭비를 피한다.

#include <stdio.h>
#define LENGTH 100

int fibonacciNumbers[LENGTH];

void initFibonacciNumbers() {
	for (int i = 0; i < LENGTH; ++i) {
		fibonacciNumbers[i] = -1;
	}
}

int fibonacci(int n) {
	printf("fibonacci(%d)가 호출되었습니다.\n", n);

	if (fibonacciNumbers[n] == -1) {
		if (n == 0) {
			fibonacciNumbers[n] = 0;
		}
		else if (n == 1) {
			fibonacciNumbers[n] = 1;
		}
		else {
			fibonacciNumbers[n] = fibonacci(n - 1) + fibonacci(n - 2);
		}
	}

	return fibonacciNumbers[n];
}

int main(void) {
	initFibonacciNumbers();

	printf("5번째 피보나치 수 = %d\n", fibonacci(5));
	printf("\n");

	return 0;
}

 

 

🚀 활용1 모든 정점 쌍 간의 최단 경로

👉 플로이드 알고리즘

 

🚀 활용2 행렬

👉 행렬의 연쇄적 곱셈 문제

👉 최장 공통 부분 수열 문제