24416번 알고리즘 수업 - 피보나치 수 1, 9184번 신나는 함수 실행 + 동적 계획법

지금부터는 동적 계획법 1이라는 문제집을 푼다. 

 

이름만 봤을 때는 감이 오진 않는다. 

 

코딩테스트 : 24416번 알고리즘 수업 - 피보나치 수 1

문제

오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.

피보나치 수 재귀호출 의사 코드는 다음과 같다.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다.

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    return f[n];
}

입력

첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.

출력

코드1 코드2 실행 횟수를 한 줄에 출력한다.

public class BackJoon
{
    private static int fibcount = 0;

    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        fib(n);
        Console.WriteLine(fibcount + 1);
        Console.WriteLine(n-2);
    }

    public static int fib(int n)
    {
        if (n == 1 || n == 2)
        {
            return 1;
        }

        fibcount++;
        return fib(n - 1) + fib(n - 2);
    }

    public static int[] fibonacci(int n)
    {
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;

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

 

서준이는 왜 그럴까 ? 

의사 코드를 바꿔봤는데, 생각해보니 그냥 그 전 배열 두 가지를 가져다 쓰는 방식이고, n의 입력이 5 이상으로 보장되어 있다면, n -2 번 수행하면 n번째 수를 구할 수 있다. 

 

중요한 점은 시행횟수의 차이가 어마어마하다는 점이다. 

 

n이 30일 때 이와 같은 차이가 난다. 

832040 28

 

결국 재귀 호출 방식을 사용하는 위의 코드는, 이미 구했던 답을 또 구하기 위해서 같은 함수를 반복 실행하지만,

( 3을 구하기 위해 1 + 1 을 실행해놓고, 4를 구하기 위해 또 1 + 1을 실행함 ) , 아래방법을 사용하면

한 번 사용했던 결과를 저장해두고 또 사용해 불필요한 계산을 줄일 수 있다. 

 

 

아마 이런 방식이 '동적 계획법'일 것 같다. 이미 풀었던 작은 문제들을 저장해두고, 또 필요해지면 가져와서 사용하는 방법!

사용할 수 있을때와 없을 때를 잘 구분해야 좋을듯 하다. 동적 계획법에 대해 따로 포스팅해서 정리할 예정이다.

 

 

https://febelo0524.tistory.com/175

동적 계획법 (Dynamic Programming, DP)

정리 완.

 

코딩테스트 : 9184번 신나는 함수 실행

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한

• -50 ≤ a, b, c ≤ 50

using System.Text;

public class BackJoon
{
    private static int fibcount = 0;

    public static void Main()
    {
        StringBuilder sb = new StringBuilder();
        while (true)
        {
            int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int a = numbers[0];
            int b = numbers[1];
            int c = numbers[2];

            if (a == -1 && b == -1 && c == -1)            
            {
                break;
            }
            sb.AppendLine( $"w({a}, {b}, {c}) = {W(a, b, c)}");
        }
        Console.WriteLine(sb.ToString());
    }

    public static int W(int a, int b, int c, Dictionary<(int,int,int), int>? dic = null)
    {
        if (dic == null)
        {
            dic = new Dictionary<(int,int,int), int>();
        }
        
        if (a <= 0 || b <= 0 || c <= 0)
        {
            return 1;
        }
        if  (dic.ContainsKey((a,b,c))) return dic[(a, b, c)];
        
        if (a > 20 || b > 20 || c > 20)
        {
            return W(20, 20, 20,dic);
        }

        if (a < b && b < c)
        {
            dic[(a,b,c)] = W(a, b, c - 1,dic) + W(a, b - 1, c - 1,dic) - W(a, b - 1, c,dic);
            return dic[(a, b, c)];
        }

        dic[(a,b,c)] = W(a - 1, b, c,dic) + W(a - 1, b - 1, c,dic) + W(a - 1, b, c - 1,dic) - W(a - 1, b - 1, c - 1,dic);
        return dic[(a, b, c)];
    }

}

 

코드 자체를 만드는 것은 어렵지 않았는데 , 동적 계획법에서 Bottom - Up 으로는 어떻게 해야할 지 감이 오지 않는다. 

그냥 인자 3개를 받고 해야 하나.. ? 

 

다른 사람의 흥미로운 풀이

 

 

다른 사람(?)인 GPT 강사님께 이 문제를 Bottom - Up 방식으로 풀고 싶은데 모르겠습니다 ! 라고 여쭈어봤다.

나온 코드는 다음과 같다.

using System;
using System.Text;

public class BackJoon
{
    static int[,,] dp = new int[21, 21, 21];

    public static void Main()
    {
        PrecomputeDP(); // 먼저 dp 배열 미리 계산

        StringBuilder sb = new StringBuilder();
        while (true)
        {
            var input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            int c = int.Parse(input[2]);

            if (a == -1 && b == -1 && c == -1)
                break;

            sb.AppendLine($"w({a}, {b}, {c}) = {GetW(a, b, c)}");
        }

        Console.WriteLine(sb.ToString());
    }

    static void PrecomputeDP()
    {
        for (int i = 0; i <= 20; i++)
        {
            for (int j = 0; j <= 20; j++)
            {
                for (int k = 0; k <= 20; k++)
                {
                    if (i == 0 || j == 0 || k == 0)
                    {
                        dp[i, j, k] = 1;
                    }
                    else if (i < j && j < k)
                    {
                        dp[i, j, k] = dp[i, j, k - 1] + dp[i, j - 1, k - 1] - dp[i, j - 1, k];
                    }
                    else
                    {
                        dp[i, j, k] = dp[i - 1, j, k] + dp[i - 1, j - 1, k] + dp[i - 1, j, k - 1] - dp[i - 1, j - 1, k - 1];
                    }
                }
            }
        }
    }

    static int GetW(int a, int b, int c)
    {
        if (a <= 0 || b <= 0 || c <= 0)
            return 1;
        if (a > 20 || b > 20 || c > 20)
            return dp[20, 20, 20];
        return dp[a, b, c];
    }
}

 

 

이번에는 하나의 '답'만을 구하는 것이 아니므로, 결과를 다 저장할 배열을 만들어두고 

그 배열을 규칙에 따라 채운다. 그 후 따로 배열의 값을 불러오는 함수를 통해 답을 도출했다. 

이렇게 보니 할만 한 듯 하다. 

이 방식을 떠올리긴 했는데 실행하지 않은 이유는 ,일단 20 , 20 , 20을 반복하는 반복문이 들어가서 

어 뭔가 아닌것 같은데.. ? 라고 생각했던게 컸다. 컴퓨터의 계산을 좀 더 믿도록 하자.

사실 20의 3제곱이라고 해 봤자 8000밖에 안되니까 ! !

 

---

else로 돌리고, return dic[(a,b,c)] 하는 것이 조금 더 깔끔한 것 같다.