알고리즘) 동적 계획법

동적계획 법

 

복잡한 문제를 여러 개의 간단한 문제로 분리하여

부분의 문제들을 해결함으로써

복잡한 문제의 답을 구하는 방법이다.

 

---

동적계획법 구현

 

1. 동적계획법이 적용 가능한지 파악

 

2. 점화식 세우기

 

ex) 피보나치수열의 점화식

fibo[i] = fibo[i-1] + fibo[i-2]

 

3. 메모이제이션 기법

 

부분 문제를 풀고 이를 DP테이블에 저장한 후,

같은 문제가 나왔을 때 재계산하지 않고  DP테이블에서

값을 불러와서 이용한다.

 

연산과 탐색이 줄어들어 시간적으로 큰 효율을 얻을 수 있다.

 

 

---

방식

 

1. 탑-다운 구현 방식

 

주로 재귀함수 형태로 코드를 구현

코드의 가독성이 좋고, 이해하기가 좋다.

 

피보나치수열 탑-다운 방식 구현

import java.util.Scanner;

class Main{
    static Scanner in = new Scanner(System.in);
    static int n = in.nextInt();

    static long[] sequence = new long[n+1];
    public static void main(String[] args) {

        //sequence배열을 모두 -1로 초기화
        for(int i=0; i<n+1; i++) {
            sequence[i] = -1;
        }

        sequence[0] = 0;
        sequence[1] = 1;

        System.out.println(getFiboNum(n));
    }
    public static long getFiboNum(int n) {
    	//이전에 계산한 적이 있는 부분은 재계산하지 않고 리턴
        if(sequence[n] != -1) {
            return sequence[n];
        }
	//메모이제이션: 구한 값을 바로 리턴하지 않고 sequence에 저장한후 리턴
        sequence[n] = getFiboNum(n-2) + getFiboNum(n-1);
        return sequence[n];
    }
}

---

100을 입력했을 때의 결과

---

2. 바텀-업 구현 방식

 

가장 작은 부분 문제부터 시작하여

큰 문제로 나아가는 방식

주로 반복문의 형태이다.

 

피보나치 수열 바텀-업 방식 구현

import java.util.Scanner;

class Main{

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        long[] sequence = new long[n+1];
        //sequence배열을 모두 -1로 초기화
        for(int i=0; i<n+1; i++) {
            sequence[i] = -1;
        }

        sequence[0] = 0;
        sequence[1] = 1;

        //반목문을 이용하여 아래에서부터 채워나감
        for(int i=2; i<n+1; i++) {
            sequence[i] = sequence[i-1] + sequence[i -2];
        }

        System.out.println(sequence[n]);
    }
}

---

100을 입력했을 때의 결과

반복문을 이용했다고 켜놓고 밥을 먹고 올필요 없다.

왜냐하면 메모이제이션으로 반복계산을 줄였기 때문이다!

하하하하

---

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

탑-다운 방식은 재귀 함수의 형태로 구현되어 있기 때문에

재귀의 깊이가 깊어질 경우 런타임 에러가 발생할 수 있다고 한다.