[0] 동적 계획법(Dynamic Programming) + 메모이 제이션

* 동적 계획법 이란?

 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

Ex) 피보나치 수열

package main; import java.util.Scanner; public class Main { static long count; public static void main(String args[]) { /* 피보나치 수열 * 처음 두항을 1과 1로 한 후, 그 다음 항 부터는 바로 앞 두 개의 항을 더해 만든 수열. * ex ) 1, 1, 2, 3, 5, 8, 13, 21 ... */ for(int i = 1; i < 35; i++) { count = 0; System.out.print(Fibonacci(i) + "\t"); System.out.printf("[%d]항을 구하기 위한 호출 회수 : %d\n", i, count); } } public static int Fibonacci(int n) { count++; if(n < 3) return 1; else return Fibonacci(n-2) + Fibonacci(n-1); } }

실행 결과

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887

[1]항을 구하기 위한 호출 회수 : 1 [2]항을 구하기 위한 호출 회수 : 1 [3]항을 구하기 위한 호출 회수 : 3 [4]항을 구하기 위한 호출 회수 : 5 [5]항을 구하기 위한 호출 회수 : 9 [6]항을 구하기 위한 호출 회수 : 15 [7]항을 구하기 위한 호출 회수 : 25 [8]항을 구하기 위한 호출 회수 : 41 [9]항을 구하기 위한 호출 회수 : 67 [10]항을 구하기 위한 호출 회수 : 109 [11]항을 구하기 위한 호출 회수 : 177 [12]항을 구하기 위한 호출 회수 : 287 [13]항을 구하기 위한 호출 회수 : 465 [14]항을 구하기 위한 호출 회수 : 753 [15]항을 구하기 위한 호출 회수 : 1219 [16]항을 구하기 위한 호출 회수 : 1973 [17]항을 구하기 위한 호출 회수 : 3193 [18]항을 구하기 위한 호출 회수 : 5167 [19]항을 구하기 위한 호출 회수 : 8361 [20]항을 구하기 위한 호출 회수 : 13529 [21]항을 구하기 위한 호출 회수 : 21891 [22]항을 구하기 위한 호출 회수 : 35421 [23]항을 구하기 위한 호출 회수 : 57313 [24]항을 구하기 위한 호출 회수 : 92735 [25]항을 구하기 위한 호출 회수 : 150049 [26]항을 구하기 위한 호출 회수 : 242785 [27]항을 구하기 위한 호출 회수 : 392835 [28]항을 구하기 위한 호출 회수 : 635621 [29]항을 구하기 위한 호출 회수 : 1028457 [30]항을 구하기 위한 호출 회수 : 1664079 [31]항을 구하기 위한 호출 회수 : 2692537 [32]항을 구하기 위한 호출 회수 : 4356617 [33]항을 구하기 위한 호출 회수 : 7049155 [34]항을 구하기 위한 호출 회수 : 11405773

* 각 항을 호출 하기 위한 점점 늘어나 효율적이지 못하다.

* 메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.

EX) 메모이제이션을 이용한 피보나치 수열

package main; import java.util.Scanner; public class Main { public static void main(String args[]) { /* 피보나치 수열 * 처음 두항을 1과 1로 한 후, 그 다음 항 부터는 바로 앞 두 개의 항을 더해 만든 수열. * ex ) 1, 1, 2, 3, 5, 8, 13, 21 ... */ int nFibo[] = new int[35]; for(int i = 1; i < 35; i++) { if(i < 3) nFibo[i] = 1; else nFibo[i] = nFibo[i-1] + nFibo[i-2]; System.out.println(nFibo[i]); } } }

실행결과

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887

* 이전 결과 값을 저장하여 가지고 있으므로 한번의 계산으로 다음 값을 구할 수 있다.