📒 갈무리 - 다이나믹 프로그래밍(Dynamic Programming)

📌 다이나믹 프로그래밍이란?(동적 계획법)

- 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다.

 

📌 Memoization

- 다이나믹 프로그래밍에서는 작은 문제들이 반복되고 이 작은 문제들의 결과 값이 항상 같기 때문에 이 점을 이용하여 한 번 계산한 작은 문제를 저장해놓고 재사용 하는 것

 

📌 다이나믹 프로그래밍 사용 조건

Ovelapping Subproblems(겹치는 작은 문제) : 다이나믹 프로그래밍은 기본적으로 문제를 부분적으로 나누고 그 문제의 결과를 재사용하여 큰 문제의 답을 구하는 것이기 때문에 동일한 작은 문제들이 반복하여 나타나는 경우에 사용할 수 있다.

Optiaml Substructure(최적 부분 구조) : 부분 문제의 최적 결과 값을 재사용하여 전체 문제의 최적 결과를 나타낼 수 있는 경우를 의미한다. 특정 문제의 결과는 문제의 크기의 상관없이 항상 동일하다.

 

📌 다이나믹 프로그래밍 사용

탑다운 방식(Top-Down)

- 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

- '하향식'이라고도 한다.

- 점화식을 이해하기 쉽다.

바텀업 방식(Bottom-Up)

- 가장 작은 문제들로부터 답을 구해가며 전체 문제의 답을 찾는 방식

- '상향식'이라고도 한다.

- 재귀 호출을 하지 않기 때문에 메모리 사용량을 줄일 수 있다.

 

📌 다이나믹 프로그래밍과 분할 정복

공통점

- 다이나믹 프로그래밍과 분할 정복은 모두 '최적 부분 구조'를 가질 때 사용할 수 있다.

차이점

- 다이나믹 프로그래밍에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

- 한 마디로, 다이나믹 프로그래밍은 작은 문제의 중복으로 인해 그 결과 값을 재사용하는 반면, 분할 정복은 단순히 큰 문제를 해결하기 위해 작은 문제로 나누어 해결하는 것일 뿐이다.

 

📌 EX) 최소 비용으로 계단 오르기

이 예제는 https://www.youtube.com/watch?v=EKHFu9vB-Oc 를 참고하였습니다.

// C#

        static void Main(string[] args)
        {
        	// 예제
            nt[] cost = { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 };
            //int[] cost = { 10, 15, 20 };
            //int[] cost = { 1, 2, 3, 4, 5, 6, 7 };
            int answer = minCost(cost);

            Console.WriteLine(answer);
        }

        public static int minCost(int[] cost)
        {
            int case1 = 0;
            int case2 = 0;
            int current;

            for (int i = cost.Length - 1; i >= 0; --i)
            {
                // 뒤에서 앞으로 오면서 현재 계단의 최소 비용을 계산
                current = cost[i] + Math.Min(case1, case2);
                case2 = case1;
                case1 = current;
                Console.WriteLine("current : " + current);
                Console.WriteLine("case2 : " + case2);
                Console.WriteLine("case1 : " + case1);
            }

            return Math.Min(case1, case2);
        }