[알고리즘] 동적 계획법(DP), 메모이제이션(Memoization) - 피보나치 수

피보나치 수 알고리즘에 대해선 일반 재귀함수/반복문 으로 푸는 방법만 알고 있었다.

이번에는 동적 프로그래밍(Dynamic Programming, DP)을 공부하면서 배열에 피보나치 수열의 값을 저장해두고 재사용하여 풀이하는 방법에 대해 공부해보았다.

💡 DP (Dynamic Programming) 동적 계획법

다이나믹 프로그래밍은 하나의 Problem이 두 개의 Sub Problem으로 나뉘고, 이러한 Sub Problem이 또 다른 Sub Problem으로 나뉜다고 할 때, 중복되는 Sub Problem이 존재하는 경우 효율적으로 문제를 해결할 수 있는 방법 중 하나이다.

 

처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식.

 

쉽게 말하자면, 배열을 만들어 값들을 저장하고, 후에 그것들을 가지고 답을 구하는 방식을 말한다.

이러한 동적계획법을 통해 문제를 해결하고자 한다면 '점화식'을 세워야 한다.
점화식이란, 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식을 말한다.
예를 들어 피보나치 수열의 점화식을 표현하면 F(n) = F(n-1) + F(n-2)로 작성할 수 있다.

 

/* 일반 재귀함수 풀이 */
int Fib(int n)
{
	if (n == 1 || n == 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

/* DP 방식을 이용한 풀이 */
int arr[50];
int Fibonacci(int n)
{
	if (n == 1 || n == 2)
	{
		arr[n] = 1;
		return arr[n];
	}

	if (arr[n] != 0)
		return arr[n];

	arr[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
	return arr[n];
}

 

 

일반적인 재귀함수를 사용한 피보나치 수열과 달리 DP 방식을 이용한 풀이는 배열을 이용한다.

 

일반 재귀함수를 통한 피보나치는 Fib(5)를 구하는 과정에서 Fib(2)가 3번, Fib(3)가 2번이나 반복된다는 점을 알 수 있다. 이러한 반복은 구하고자 하는 피보나치 수열이 커질수록 기하급수적으로 증가하게 된다.

 

이때 메모이제이션(Memoization) 기법을 사용하여 동일한 계산을 반복하는 컴퓨터 프로그램을 개선시킬 수 있다.

이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 증가시킬 수 있다. 피보나치 수열을 풀이할 때 사용하는 '배열 사용'도 메모이제이션 기법의 예시 중 하나이다.

 

따라서 동적계획법을 이용한 풀이에는, 초기 조건으로 Fibonacci(1) = Fibonacci(2) = 1 을 설정한 뒤, 배열의 값이 0이 아니라면(이미 값이 저장되어 있다면) 배열에 저장된 값을 단순히 불러와 사용하고, 배열이 초기화되어 있지 않은 경우에만 Fibonacci 함수를 통해 값을 저장해주었다.

⏱️ 시간복잡도

일반 재귀함수를 통해 풀이한 프로그램의 경우, 높이가 n인 트리의 총 노드 수는 2^n-1 이다.

따라서 Fib(n)의 시간 복잡도는 O(2^n-1) = O(2^n) 이다.

DP를 이용해 풀이한 프로그램은 이미 가지고 있는 값에 대해 재귀호출 하지 않고 값만 반환하기 때문에 2번씩 반복할 필요가 없어진다. 따라서 시간복잡도 O(n)을 갖는다.

---

참조

https://sectumsempra.tistory.com/86

[C++ 알고리즘] 동적 계획법(Dynamic Programming)

https://chanos.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%99%84%EB%B2%BD%ED%9E%88-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

[자료구조] 피보나치 수열의 시간 복잡도 완벽히 이해하기