알고리즘) 동적 계획법 (Dynamic Programmi

동적 계획법 (Dynamic Programming)

어떤 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(Sub Problem)로 나누어서 푼 다음에 그걸 결합해서 최종적인 목적에 도달하는 것이다. 복잡한 문제를 처음부터 풀기보다는 조금씩 조금씩 만들어서 풀면 쉽게 풀리기도 한다.

동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그중에서 최적을 풀이법을 찾아내기 때문이다.

1. 전체 문제를 작은 문제로 단순화한다.

2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다.

3. 작은 문제를 해결한 방법들을 결합한다.

4. 문제를 해결한다.

-----------------------------------------------------------------------------------------------------------------------------------

동적 계획법에서는 메모 이제이 션(Memoization)이 중요한 개념인데.

계산된 값을 저장해서 다음에 값을 활용한다.

동적 계획법을 사용한 문제를 예시로 보면 다음과 같다.

가장 왼쪽 상단(0,0)에서 가장 오른쪽 하단 (4,4) 이동을 한다.

이동에 대한 판단을 하는 과정에서는 (가로, 세로 이동만 가능) 큰 수치가 있는 곳으로 간다.

동적 계획법을 활용하면 최적의 경로를 찾는 것이 가능하다.

테스트 코드는 다음과 같다.

 private void DynaimcProgramTest()
    {

        int[,] value = {
            {3, 7, 9, 2, 7},
            {9, 8, 3, 5, 5},
            {10, 7, 9, 8, 5},
            {3, 8, 6, 4, 10},
            {6, 3, 9, 7, 8}
        };

        int [,] sum = new int[ value.GetLength(0), value.GetLength(1)];

        int colSum = 0;
        int rowSum = 0;

        for (int i = 0; i < value.GetLength(0); i++)
        {
            colSum += value[i,0];
            sum[i, 0] = colSum;
        }
        for (int i = 0; i < value.GetLength(1); i++)
        {
            rowSum += value[0 , i];
            sum[0 , i] = rowSum;
        }

        for (int i = 1; i < value.GetLength(0); i++)
        {
            for (int j = 1; j < value.GetLength(1); j++)
            {
                if (sum[i, j- 1] > sum[i - 1 , j])
                {
                    sum[i, j] = sum[i, j - 1] + value[i, j];
                }
                else
                {
                    sum[i, j] = (sum[i - 1, j] + value[i, j]);
                }
            }
        }

        Logger.LogFormat(" Sum [4,4] : {0}", sum[ value.GetLength(0)-1, value.GetLength(1) - 1]);
    }

실제 계산된 데이터를 합산으로 보면 다음과 같다.