알고리즘 ] 5. DP

1. Dynamic Programming

- 별 의미는 없다고 함.

 

1) 피보나치 기본 재귀

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>

using namespace std;

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

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

 

2) memoization

- 이미 계산했던 것을 기록하여 반복량을 줄이는 방법

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> dp;
int cnt = 0;

int fibonacci(int n)
{
	cnt++;
	if (n == 0) {
		return 0;
	}
	if (n == 1) {
		return 1;
	}
	if (dp[n] != -1) {
		return dp[n];
	}
	dp[n] = fibonacci(n - 2) + fibonacci(n - 1);		
	return dp[n];
}

int main()
{
	dp.resize(10, -1);
	for (int i = 0; i < 10; i++)
	{
		printf("%d\n", fibonacci(i));
	}

	printf("=> %d", cnt);
}

 

 

2. 연습문제

- https://www.acmicpc.net/problem/1463

- 위와 같으 Memorization 방식을 사용해서 연산을 줄여주었다.

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>
#include <vector>
#define MAXSIZE 1000001

using namespace std;

vector<int> dp;


int makeOne(int n)
{
	int cnt = 0;
	if (n <= 1)
	{
		return cnt;
	}	
	if (dp[n] != -1)
	{
		return dp[n];
	}

	int tmp = makeOne(n - 1) + 1;
	cnt = tmp;
	
	if (n % 3 == 0)
	{
		tmp = makeOne(n / 3) + 1;
		if (tmp < cnt)
		{
			cnt = tmp;
		}
	}

	if (n % 2 == 0)
	{
		tmp = makeOne(n / 2) + 1;
		if (tmp < cnt)
		{
			cnt = tmp;
		}		
	}
	dp[n] = cnt;

	return cnt;
}

int main()
{
	dp.resize(MAXSIZE, -1);
	int result = makeOne(854);
	cout << result;
}