algorithm-theory-Dynamic-programming

Dynamic Programming

정의

  • 동적 계획법
    • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
    • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
    • Memoization 기법을 사용함
      • Memoization : 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
    • 문제를 잘게 쪼겔 때, 부분 문제는 중복되어, 재활용됨.
      • 예: 파보나치 수열

피보나치 수열

동적 계획법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Fibonachi {
// dynamic programing
public int fibonachi(int num){
    if(num == 0) return 0;
    else if(num == 1) return 1;
    return fibonachi(num - 1) + fibonachi(num - 2);
}

public static void main(String[] args) {
//        fibonacci(0):0
//        fibonacci(1):1
//        fibonacci(2):1
//        fibonacci(3):2
//        fibonacci(4):3
//        fibonacci(5):5
//        fibonacci(6):8
//        fibonacci(7):13
//        fibonacci(8):21
//        fibonacci(9):34
        Fibonachi fibo = new Fibonachi();
        System.out.println(fibo.fibonachi(9));
    }
}