1 만들기(Dynamic Programming )

 

1. 다이나믹 프로그래밍이란 (Dynamic Programming )

 

가장 익숙한 다이나믹 프로그래밍의 예는 재귀함수를 배울때 피보나치 수열에서 배웠다. 

 

int Fi(int num)
{

   if(num == 1)
      return 1;
   else if( num ==2 )
      return 1;
   else
      return Fi(num-1)+Fi(num-2);

}

 

위의 피보나치 수열 처럼 어떠한 문제는 작은 문제들의 합이 될수 있다는 개념이 다이나믹 프로그래밍의 기초이다. 

 

위의 F 는 여러개의 작은 sub F 로 풀 수 있다. 

 

피보나치 수열에서 한것처럼 위에서 부터 F 를 나눠서 플어나가는 방식을 Top-down 방식이라고 한다. 

 

 

위와 같은 Top-down 방식은 함수를 계속해서 호출해야 되어서 나중에는 스택오버 플로우 문제를 야기할 수  있다. 

그리고 위의 F(3) 의 경우 왼쪽에서 1번 계산하지만 오른쪽 줄기에서도 계산해야 한다 이미 F(3) 의 값을 계산했는데 한번더 하는것은 프로그램의 속도를 줄일 뿐이다. 

이러한 부분을 보완하기 위해서 Bottom - up  방식이 존재한다. 

 

Bottom - up

Bottom -up 방식이란 Top-dowm 방식과는 반대로 및에서부터 위로 올라가는 방식이다. 

 

항상 F(n) 의 값을 갖는 배열을 정의한다음 

F(1) 부터 차례대로 구하는 것이다. 결국 F(n) 까지 구하개되면 프로그램은 끝나고 시간 복잡도는 0(n) 이된다. 

 

밑의  예제를 보면서 Bottom-up  에 대해서 이해해 보자 

 

 

 

예제 1 )

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

1463번: 1로 만들기

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

// dp botton up 방식
int main(void)
{
	int Num ;
	
	cin >> Num;

	int* dp_array = (int*)malloc(sizeof(int)* (Num + 1));
	memset(dp_array, 0, sizeof(int) * (Num + 1));

	dp_array[1] = 0;

	if (Num > 1)
	{
		for (int i = 2; i <= Num; i++)
		{
			dp_array[i] = dp_array[i - 1] + 1;
			if (0 == (i % 2))
			{
				dp_array[i] = min(dp_array[i], dp_array[i / 2] + 1);
			}
			if (0 == (i % 3))
			{
				dp_array[i] = min(dp_array[i], dp_array[i / 3] + 1);
			} // 모든 경우의 수를 비교하기 위해서 if 쓴다 

		}
	}

	cout << dp_array[Num];

	return 0;
}

2 로 나뉘는 경우 , 3으로 나뉘는 경우 -1 하는경우 모든 경우의 수를 비교해야 한다. 

 

예제 2 )

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

#include<iostream>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>> triangle_copy;

    if (0 == triangle.size()) { return triangle[0][0]; } // 삼각형의 높이가 1 이면 꼭대기 값 return 

    for(int  i = (triangle.size()-2); i >=0; i--)
    {
        for (int j = 0; j < triangle[i].size(); j++)
        {
			triangle[i][j] = triangle[i][j] + max(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    answer = triangle[0][0];
    return answer;
}

int main()
{
    vector<vector<int>> triangle = { vector<int>{7}, vector<int>{3, 8}, vector<int>{8, 1, 0}, vector<int>{2, 7, 4, 4},vector<int>{4, 5, 2, 6, 5}};
    cout << solution(triangle);

	return 0;
}

예제 3

등굣길 

https://programmers.co.kr/learn/courses/30/lessons/42898#

코딩테스트 연습 - 등굣길

효용성에서 틀리는데 ;; 느리다누 ㅠㅠ

#include<iostream>
#include <string>
#include <vector>

using namespace std;

//void printMap(int** map, int m, int n)
//{
//    for (size_t i = 0; i < n; i++)
//    {
//        for (size_t j = 0; j < m; j++)
//        {
//            cout << map[i][j];
//        }
//        cout << endl;
//    }
//}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;

    int** map = new int*[n];
    // 동적 할당
    for (size_t i = 0; i < n; i++)
    {
        map[i] = new int[m];
    }
     
    // 데이타 초기화 
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < m; j++)
        {
            map[i][j] = 0;
        }
    }
    // puddles  인 곳은 -1 저장 
    for (size_t i = 0; i < puddles.size(); i++)
    {
		map[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
    }

    // 외각 은 무조건 1 
	map[n - 1][m - 1] = 1;

    //printMap(map, m ,n );
    if (1 != m && 1 != n) // 1줄만 있는경우 제외 
    {
        for (int i = n - 1; i > -1; i--)
        {
            for (int j = m - 1; j > -1; j--)
            {
                if (-1 == map[i][j])
                {
                    continue;
                }
                if ((j + 1) <= ( m - 1))
                {
                    if (-1 != map[i][j + 1])
                    {
                        map[i][j] = map[i][j] + map[i][j + 1];
                    }
                }
                if ((i + 1) <= (n - 1))
                {
                    if (-1 != map[i + 1][j])
                    {
                        map[i][j] = map[i][j] + map[i + 1][j];
                    }
                }

            }
        }
        //printMap(map, m, n);
        answer = map[0][0];
    }
    else
    {
        answer = 1;
    }

    // 동적 할당 해제 
    for (size_t i = 0; i < n; i++)
    {
        delete  map[i];
    }
    delete[] map;

    return answer;
}

int main()
{
    vector<vector<int>> a = { {2, 2},{1,2},{3,2},{4,2} };
    vector<vector<int>> b = { {2, 2}};

    cout << solution(4, 3, a);

    return 0;
}