동적계획법 DP 구현방법 ( + [백준] 11050 이항계수 문제풀이)

 

11050번: 이항 계수 1

 + 이항계수?

경우의 수를 계산할 때 사용한다.

결론부터 말하면 아래와 같이 팩토리얼로 계산할 수 있다.

 

 

팩토리얼 재귀함수로 풀어보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int result = fact(n) / (fact(k) * fact(n-k));
        System.out.println(result);

    }

    private static int fact(int num) {
        if(num == 1 || num == 0){
            return 1;
        }
        return fact(num-1) * num;
    }
}

 

재귀함수는 fact(5) 호출 후 fact(5)를 호출하면 다시 계산해서 값을 구한다.

fact(5)를 호출하면 아래와 같이 동작한다

 

여기서 다시 fact(5)를 호출하면? 똑같이 사진의 연산을 반복할 것이다.

이것을 저장해서 값을 재사용하자는게 DP이다.

 

 

 

동적계획법 Dynamic Programming

동적계획법은 큰 문제를 작게 쪼개어 연산하고, 연산한 결과를 저장했다가 다시 사용하는 것이다.

 

DP를 사용하여 위의 문제를 다시 풀어보자

 

 

 

팩토리얼 재귀함수와 DP 사용하여 풀어보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main11050 {
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        dp = new int[n+1];

        int result = fact(n) / (fact(k) * fact(n-k));
        //System.out.println(Arrays.toString(dp));
        System.out.println(result);

    }

    private static int fact(int num) {
        if(dp[num] > 0){
            //System.out.println(num+"! found");
            return dp[num];
        }

        if(num == 1 || num == 0){
            dp[num] = 1;
            return dp[num];
        }

        dp[num] = fact(num-1) * num;
        //System.out.println(num + "! save");
        return dp[num];
    }
}

print문 주석을 풀고, fact(5)를 호출하면 아래와 같이 출력된다

2! save
3! save
4! save
5! save
2! found ⭐ 이미 연산한 fact(2)를 불러온다
3! found ⭐ 이미 연산한 fact(3)를 불러온다

 

 

DP를 사용하면 다시 연산하지 않아도 되니 실행 속도도 빨라지게된다.

DP는 재귀함수에서 가장 흔하게 사용할 수 있다. 하지만 재귀함수에만 한정된 방법은 아니란 것을 알고있자!