[동적 계획법] 동적 계획법

✔ 동적 계획법

동적 계획법이란?

• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법
• 동적 계획법은 다음을 만족할 때 사용
  • 큰 문제를 작은 문제로 나눌 수 있어야 함
  • 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 함
  • 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용함 (메모이제이션 기법)
  • 톱-다운 방식과 바텀-업 방식으로 구현할 수 있어야 함

피보나치 수열이란?

• 각 항이 바로 앞의 두 항을 이루어진 수열

피보나치 수열로 동적 계획법 이해하기

1. 동적 계획법으로 풀 수 있는지 확인하기
   • 6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합
   • 즉, 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고,
     수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있음
2. 점화식 세우기
   • 점화식을 세우기 위해서는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는        훈련이 필요
   • 피보나치 수열의 점화식은 D[i] = D[i - 1] + D[i - 2]
3. 메모이제이션 원리 이해하기
   • 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고
     다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것
   • 불필요한 연산과 탐색이 줄어들어 시간복잡도 측면에서 많은 이점을 가질 수 있음
4. 구현 방식 이해하기
   • 톱-다운 구현 방식은 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수 형태로 구현
     코드의 가독성이 좋고, 이해하기 편리하다는 장점이 있음
   • 바텀-업 구현 방식은 가장 작은 문제부터 해결하면서 점점 큰 문제로 확장해 나가는 방식으로, 주로 반복문 형태로 구현
   • 두 방식 중 좀 더 안전한 방식은 바텀-업 구현 방식
   • 톱-다운 구현 방식은 재귀 함수의 형태로 구현돼 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생
   • 자신에게 좀 더 편한 방식이나 문제에 따라 두 방식 중 1개를 선택해 사용

// 톱-다운 구현 방식 (재귀 함수)
public class 피보나치수_톱_다운 {
    static int[] D;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        D = new int[n + 1];
        // DP 테이블 초기화
        for (int i = 0; i <= n; i++) {
            D[i] = -1
        }
        // 이미 아는 가장 작은 문제 저장
        D[0] = 0;
        D[1] = 1;
        fibo(n);
        System.out.println(D[n]);
    }
    
    static int fibo(int n) {
        // 기존에 계산한 적이 있는 부분의 문제는 재계산하지 않고 리턴
        if(D[n] != -1) 
            return D[i];
        // 구한 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴
        return D[n] = fibo(n - 2) + fibo(n - 1);
    }
}

// 바텀-업 구현 방식 (반복문)
public class 피보나치수_바텀_업 {
    static int[] D;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        D = new int[n + 1];
        // DP 테이블 초기화
        for (int i = 0; i <= n; i++) {
            D[i] = -1
        }
        // 이미 아는 가장 작은 문제 저장
        D[0] = 0;
        D[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 구한 값을 DP 테이블에 저장
            D[i] = D[i - 1] + D[i - 2];
        }
        System.out.println(D[n]);
    }
}

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn