코딩 테스트 대비: 동적 프로그래밍 기초 (C#)

안녕하세요, GameLabMaster입니다! 오늘의 포스팅에서는 동적 프로그래밍에 대해 이해하고, 이를 활용한 문제 해결 방법을 살펴보겠습니다. 동적 프로그래밍은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법입니다. 이 방법은 큰 문제를 해결하기 위해 작은 문제를 여러 번 해결하는 상황에서 효율적입니다.

 

문제
0부터 N까지의 숫자에서 i번째 피보나치 수를 구하는 프로그램을 작성하세요.

 

입력

• 숫자 N (0 ≤ N ≤ 100)

출력

• N번째 피보나치 수

풀이
동적 프로그래밍을 이용하여 피보나치 수열을 구하는 문제를 해결할 수 있습니다. 피보나치 수열의 i번째 항은 (i-1)번째 항과 (i-2)번째 항의 합이므로, 이전에 계산한 결과를 활용하여 현재의 문제를 해결할 수 있습니다.

 

다음은 C#으로 작성한 동적 프로그래밍을 이용한 피보나치 수열 구하기 코드입니다.

 

using System;

public class Program
{
    static long[] dp = new long[101];

    public static long Fibonacci(int n)
    {
        if (n <= 1)
            return n;
        else if (dp[n] != 0)
            return dp[n];
        else
            return dp[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
    }

    public static void Main(string[] args)
    {
        int n = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine(Fibonacci(n));
    }
}

 

이 코드는 동적 프로그래밍의 기본 개념을 이용하여 피보나치 수열을 구하는 것을 보여줍니다. dp 배열은 이전에 계산한 피보나치 수열의 값을 저장하여, 같은 계산을 반복하지 않도록 합니다. 이렇게 동적 프로그래밍을 이용하면 같은 문제를 반복해서 풀 필요 없이 한 번만 풀어서 시간을 절약할 수 있습니다.

 

다음 포스팅에서는 동적 프로그래밍을 이용한 다른 문제들을 살펴보도록 하겠습니다.