[알고리즘] 동적 계획법 (메모이제이션 & DP)

치치·2025년 1월 21일

알고리즘

알고리즘C++

목록 보기

13/24

동적 계획법

특정 범위까지의 값을 구하기 위해서 작은 범위의 값을 이용하여 효율적으로 값을 구하는 알고리즘이다
이미 계산된 결과(작은 문제)는 별도의 메모리 공간에 저장해두어 다시 계산하지 않도록 한다
-> 하나의 문제는 단 한번만 계산하도록 하는 알고리즘

해당 조건을 만족하는 곳에서 사용하면 효율적이다

최적 부분 구조
(탐욕법에서도 말한 부분이다)
전체 문제의 최적 방법이 부분 문제의 최적 방법으로 구성된 문제 구조
중복 부분 문제
동일한 작은 문제를 반복적으로 해결하는 문제

동적 계획법 구성

메모이제이션 - Top-Down 방식 (하향식)
다이나믹 프로그래밍 (DP) - Bottom-Up 방식 (상향식)

피보나치 수열 예시

피보나치 수열이란?
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...로 이어지는 수의 배열이다
예를 들자면, 위의 배열에서 8은 앞의 3 + 5의 값이다
[1]과 [2]인덱스는 값이 1이다. [0]이하는 0
N = (N - 1) + (N - 2) 의 공식을 따른다

일반적인 재귀를 사용 (메모이제이션 사용x)

#include <iostream>
#define SIZE 100001
using namespace std;

// 피보나치 수열 구현

// 2. 일반 재귀 사용 (메모이제이션x) 
int Fibonacchi2(int n)
{
	if (n <= 0)
	{
		return 0;
	}
	else if (n <= 2)
	{
		return 1;
	}

	return Fibonacchi2(n - 1) + Fibonacchi2(n - 2);
}

int main()
{
		int array[SIZE] = { 0, };
        
		cout << Fibonacchi2(43) << endl;
}

시간복잡도가 O(N²)
이미 계산해서 알고있는 값이어도 저장 되어 있지 않기 때문에,
계속 중복된 함수가 호출된다

결과값: 결과값은 제대로 나오지만 실행 속도가 느리다

메모이제이션

프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장하여, 동일한 계산을 반복 수행하는 작업을 제거하여 프로그램 실행 속도를 향상시키는 방법이다

저장된 값을 캐시라고 하며, 중간에 저장되는 과정을 캐싱이라고 한다
메모이제이션 기법은 주로 Top-Down 방식 (하향식) 에서 사용한다

Top - Down 방식이란?
-> 큰 문제를 작은 문제로 호출하여 작은 문제들을 해결해나가는 것
-> 큰 값부터 계산하고, 작은 값들을 재귀적으로 내려가면서 필요한 값을 차례로 계산한 뒤 저장하는 방식이다

예를 들어, 피보나치 수열을 구하는 함수에서 list[4]를 호출하였다

가장 큰 문제인 4를 호출하고 재귀적으로 3, 2, 1이 호출된다
작은 문제들의 값들이 먼저 저장되면서 해결되면 큰 문제의 값을 구할 수 있게 된다
즉, 큰 문제인 4를 함수로 호출하게 되면 작은 문제들의 재귀 함수가 호출되고 작은 문제들의 함수들을 해결하여 값을 저장한 뒤, 마지막에 큰 문제의 함수가 작은 문제들의 값을 토대로 계산되고 종료된다

메모이제이션을 사용한 하향식

#include <iostream>
#define SIZE 100001
using namespace std;

// 피보나치 수열 구현

// 1. Top - Down방식 (메모이제이션0)
int Fibonacchi(int n, int list[])
{
	// 이미 계산된 값은 list[n]에 저장
	if (n <= 0)
	{
		return 0;
	}
	else if (n <= 2)
	{
		return 1;
	}

	if (list[n] != 0)
	{
		return list[n];
	}

	return list[n] = Fibonacchi(n - 1, list) + Fibonacchi(n - 2, list);

}
int main()
{
	int array[SIZE] = { 0, };

	cout << Fibonacchi(43, array) << endl;
}

메모이제이션을 사용한 피보나치 수열 구하기는 실행시간이 빠르다

Top - Down (하향식) 장점

큰 값부터 계산하고, 작은 값을 재귀적으로 내려가면서 필요한 값을 차례로 계산하고 저장한다
부분 문제를 풀 때 마다 결과 값을 저장하기 때문에 메모리 사용이 효율적이다
중복 계산을 제거한다
시간복잡도는 O(N)이다

DP

주로 재귀를 사용하지 않고, 기존의 배열을 채워나가는 식의 Bottom-Up 방식 (상향식)을 사용한다

Bottom-Up 방식이란?
-> 부분 문제를 풀 때마다 결과값을 기존의 배열에 저장해나간다
-> 작은 값부터 계산하면서 큰값을 얻어낸다
-> 먼저 계산한 값(작은 값)을 사용하여 반복문을 실행한다

아래의 코드를 보면, 피보나치 배열에서 구하고 싶은 n번째 인덱스의 값을 알기 위해선
array[0] 부터 순서대로 값을 배열에 저장한 뒤, n번째의 값을 구한다

#include <iostream>
#define SIZE 100001
using namespace std;

// 3. Bottom - Up 방식 (DP)
void Fibonacchi3(int n)
{
	int * array = new int[n + 1] {0, };

	// 인덱스[1] 이하의 값은 1
	array[0] = 0;
	array[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		array[i] = array[i - 1] + array[i - 2];
	}

	cout << array[n];

	delete [] array;
}

int main()
{
	Fibonacchi3(43);
}

결과값은 제대로 나온다

Bottom-Up 방식 (상향식) 장점

한번의 반복문을 사용하기 때문에 시간복잡도는 선형시간 O(N)
배열을 사용하여 저장해 나가기 때문에, 메모리 사용은 N에 비례한다 -> 공간복잡도 O(N)
재귀함수를 사용하지 않고 반복문을 사용하기 때문에 스택 오버플로우의 위험성이 없다

비교

메모이제이션과 DP 모두 시간복잡도는 O(N)이다
둘 다 일반적인 재귀함수 사용에 비해 실행속도가 빠르다
하지만, 메모이제이션 기법은 DP에 비해 하위 재귀함수 호출과 스택 오버플로우 때문에 조금 느릴 수 있다

메모이제이션 피보나치 수열 다시보기

#include <iostream>
#define SIZE 10
using namespace std;

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

// 메모이제이션을 사용하여 피보나치 수열 구하기
// 피보나치 수열 : 0 1 1 2 3 5 8 ---

int Fibonacci(int n, int list[])
{
	if (n <= 0) // [0]
	{
		return 0;
	 }
	else if (n <= 2) // [1], [2]
	{
		return 1;
	}

	if (list[n] != 0)
	{
		return list[n];
	}

	// 재귀를 사용하여 list[n]에 저장
	list[n] = Fibonacci(n - 1, list) + Fibonacci(n - 2, list);
}




int main()
{
	int list[SIZE] = { 0, };

	// 인자값으로 보내는 n은 인덱스의 값
	cout << Fibonacci(6, list);

	return 0;
}