Dynamic Programming 동적 계획법

동적 계획법은 복잡한 문제를 여러개의 간단한 문제로 분리해

부분문제를 해결함으로 복잡한 문제의 답을 구하는 방법을 의미한다.

 

핵심 이론은

① 큰 문제를 작은 문제로 나눈다.

② 작은 문제들이 반복되고, 작은문제들의 결과값은 항상 같아야한다.

③ 모든 작은문제는 한번만 계산돼 DP 테이블에 저장한 뒤 재사용할때는 이 테이블을 이용한다

 

동적계획법에는 두가지 방식 탑다운 방식과 , 바텀업 방식으로 나눠진다.

 

탑다운

문제를 파악하고 점차 내려오는 방식으로, 주로 재귀함수 형태로 코드를 구현한다.

이 방식은 코드의 가독성이 좋고, 이해하기 편한 장점이 있다.

int[] memo;

int Fibo(int n) {
    if (memo[n] != -1) return memo[n];
    if (n <= 1) return memo[n] = 1;
    return memo[n] = Fibo(n - 2) + Fibo(n - 1);
}

주어지는 n부터 n-2 n-1 로 내려오며, 재귀 호출형식

 

바텀업

작은 부분부터 큰문제로 확장하는 방식

int[] memo;

memo[1] = 1;

int Fibo(int n)
{
    for (int i = 2; i < n; i++)
    {
        memo[i] = memo[i-2] + memo[i-1];
    }
}

 

 

두 방식중 좀 더 안전한 방식은 바텀업 방식이다.

탑다운 방식은 재귀 함수형태로 깊이가 깊어질수록 런타임 에러가 발생될수있다.

코딩 테스트에서 런타임 에러가 발생할정도의 난이도 문제는 많이 없지만,

버그가 발생했을시 재귀호출특성상 디버깅이 어려워질수도 있다.

 

문제 https://www.acmicpc.net/problem/2193

2193번: 이친수

 

풀이

int input = int.Parse(Console.ReadLine());

long[,] dp = new long[input,2];

dp[0,1] = 1;

for (int i = 1; i < input; i++)
{
    dp[i,0] = dp[i-1,0] + dp[i-1,1];
    dp[i,1] = dp[i-1,0];
}

System.Console.WriteLine(dp[dp.GetLength(0)-1,0] + dp[dp.GetLength(0)-1,1]);