[ 동적 계획법 ] DP(Dynamic Programming, 백준 2747, 11726)

 DP(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 분리하여 부분의 문제들을 해결해 최종적으로 복잡한 문제의 답을 구한다.

 

💡 동적 계획법(DP)의 핵심 이론

1️⃣  동적 계획법의 원리와 구현 방식

 

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
   -> 메모이제이션 기법
4. 동적 계획법은 톱-다운 방식(top-down)과 바텀-업(bottom-up) 방식으로 구현할 수 있다.

 

2️⃣  피보나치 수열(동적 계획법의 가장 대표적인 문제)

피보나치 수열 공식
D[N] = D[N-1] + D[N-2]

 

1. 동적 계획법으로 풀 수 있는지 확인하기
   6번째 피보나치 수열을 구하는 문제는 5, 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고,
   수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.
2. 점화식 세우기
   논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.
3. 메모이제이션 원리 이해하기
   부분 문제를 풀었을 때 이 문제를 DP테이블에 저장해놓고 다음에 같은 문제가 나왔을 때 다시 계산하지 않고 DP테이블의 값을 재사용한다.
4. 톱-다운 구현 방식 이해하기
   문제를 위에서부터 파악해 내려오는 방식이다. 주로 재귀 함수 형태로 코드를 구현한다.

 

 2747 : 피보나치 수

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 F_n = F_n-1 + F_n-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

입력	출력
10	55

 

문제 풀이

• D[N] = D[N-1] + D[N-2]를 사용하여 재귀함수로 푼다.
  
  

실행 코드

ⓐ top-down 방식 : 큰 값에서 작은 값을 구하는 방식
     -> 재귀의 깊이가 매우 깊어지면 런타임 에러가 발생할 수 있다.

import java.util.Arrays;
import java.util.Scanner;

public class P2747_Fibonacci {
    static int[] D;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        D = new int[N+1];
        Arrays.fill(D, -1);
        D[0] = 0;
        D[1] = 1;
        fib(N);
        System.out.print(D[N]);
    }
    //피보나치 배열 채우기
    public static int fib(int n) {
        if(D[n] != -1) return D[n]; //계산을 이미 했으면 그냥 리턴
        return D[n] = fib(n-1) + fib(n-2);
    }
}

 

ⓑ bottm-up 방식 : 가장 작은 값부터 올라가는 방식

import java.util.Arrays;
import java.util.Scanner;

public class P2747_Fibonacci_bottomUp {
    static int[] D;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        D = new int[N+1];
        Arrays.fill(D, -1);
        D[0] = 0;
        D[1] = 1;
        fib(N);
        System.out.print(D[N]);
    }
    //피보나치 배열 채우기
    public static void fib(int N) {
        for(int i=2;i<=N;i++) {
            D[i] = D[i-1] + D[i-2];
        }
    }
}

 

 

 

 11726 : 2 X n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

입력	출력
2	2
9	55

 

문제 풀이

• 점화식 구하기
  D[N] = 길이 N으로 만들 수 있는 타일의 경우의 수
  D[N] = D[N-1] + D[N-2] 
• 런타임 에러 (ArrayIndexOutOfBounds)
  만약에 n이 1일 때 배열이 D[0], D[1]까지밖에 안만들어지는데 밑에서 초기화를 D[2]해주니까.....낫음...
  

 

 

실행 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[N+1];
        if(N == 1) {
            System.out.println(1);
            return;
        }
        if(N == 2) {
            System.out.println(2);
            return;
        }
        D[1] = 1;
        D[2] = 2;
        for(int i=3;i<=N;i++) {
            D[i] = (D[i-1] + D[i-2]) % 10007;
        }
        System.out.print(D[N]);
    }
}

 

아무래도 나 점화식 못세울듯ㅋㅋ