2022.01.28 [백준] C# 피보나치 수 5

 

 

 

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

10870번: 피보나치 수 5

 

---

동적 계획법(Dynamic Programming) 

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제(하위 문제)로 나누어 풀고, 그것을 결합하여 최종적인 문제를 해결하는 것이다. 이때 각 하위 문제들의 답을 저장해놓고 같은 하위 문제가 나타난다면 미리 구한 답을 이용하면 된다. 분할 정복(Divide and Conquer) 방식과 비슷하지만 분할 정복은 하위 문제가 중복되지 않는다는 점이 다르다. 

 

메모이제이션(Memoization)

동일한 문제를 반복해야 할 경우, 미리 계산해서 저장해 둔 결과를 활용하여 중복 연산을 줄이는 방식을 메모이제이션이라고 한다.  동적 계획법은 중복되는 하위 문제를 메모이제이션을 이용해 효율적으로 해결할 수 있다. 

출처: https://code-lab1.tistory.com/7 [code_lab]

풀이

 

- 정답 코드 1

using System;
class Program
    {
        static int Fiboncci(int n)
        {
 
            if (n < 2)
            {
                return n;
            }
            else
            {
                return Fiboncci(n - 1) + Fiboncci(n - 2);
            }
            
        }
        
        
 
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(Fiboncci(n));
        }
    }

- 정답 코드 2

using System;
class Program
    {
        static int[] num = new int[21];
 
        static int Fiboncci(int n)
        {
            
            num[0] = 0;
            num[1] = 1;
            if (n < 2)
            {
                return num[n] ;
            }
            if (num[n] != 0)
            {
                return num[n];
            }
            num[n] = Fiboncci(n - 1) + Fiboncci(n - 2);
            return num[n];
 
 
 
        }
        
        
 
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(Fiboncci(n));
        }
    }

위 코드는 다이나믹 프로그래밍을 이용한 Top-down방식을 이용한 재귀함수를 사용했다.

시간은 아래 코드가 조금 더 걸리지만 n값이 커지면 계산이 많이 증가한다. 그래서 다이나믹 프로그래밍을 이용하여 복잡한 문제를 여러 개의 간단한 문제(하위 문제)로 나누어 풀고,  각 하위 문제들의 답을 저장해놓고 같은 하위 문제가 나타난다면 미리 구한 답을 이용하면 된다.