공부방
동적계획법(DP) 본문
재귀 함수를 이용한 피보나치 수열
package day0410_동적계획법;
import java.util.Scanner;
public class 피보나치 {
static long callFibo1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
System.out.println(fibo1(N));
System.out.println(callFibo1);
}//main
//재귀 함수를 이용한 피보나치
public static long fibo1(int n) {
callFibo1++;
if(n<2)return n;
return fibo1(n-1)+fibo1(n-2);
}
}
//10 입력하면
10
55
177메모이제이션(Memoization)
- 메모이제이션은 컴퓨터 프로그램을 실행할 때, 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다.
- 동적 계획법의 핵심이 되는 기술
package day0410_동적계획법;
import java.util.Arrays;
import java.util.Scanner;
public class 피보나치 {
static long callFibo1, callFibo2;
static long[] memo;
//이렇게 static 박스를 사용하여 가능
static {
memo = new long[10000];
memo[0] = 0;
memo[1] = 1;
//미리 계산을 해놓고
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
memo = new long[N+1]; //0으로 초기화가 되어있다.
// Arrays.fill(memo, -1);
// memo[0]=-1;//위의 코드를 살리면 이 한 줄이 필요
memo[1] = 1;
System.out.println(fibo1(N));
System.out.println(callFibo1);
System.out.println(fibo2(N));
System.out.println(callFibo2);
}//main
//재귀 함수를 이용한 피보나치
public static long fibo1(int n) {
callFibo1++;
// if( memo[n] ==-1) { //위의 주석을 풀어버리면 요런게 가넝
if(n<2)return n;
return fibo1(n-1)+fibo1(n-2);
}
//memoization 기법을 적용한 피보나치
public static long fibo2(int n) {
callFibo2++;
if( n>=2 && memo[n] ==0) {
memo[n] = fibo2(n-1)+fibo2(n-2);
}
return memo[n];
}
}
//10 입력하면
10
55
177
55
19단점
- 추가적인 메모리 공간 필요
- 재귀 함수 호출로 인한 시스템 호출 스택을 사용->실행 속도 저하 또는 오버플로어가 발생할 수 있음.
동적 계획 알고리즘
- 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
- 최적화 문제 : 최적(최대값이나 최소값 같은) 값을 구하는 문제
- 해당 문제에 여러 해가 있을 수 있다.
- 특정한 최적해를 구하는 것이 아니라 어떤 최적해를 구하는 것이다.
- 동적 계획 알고리즘은 먼저 작은 부분 문제들의 해들을 구하고, 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.
동적계획법의 적용 요건
- 중복 부분 문제 구조
- 최적 부분 문제 구조
중복 부분 문제 구조
- DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고, 작은 문제들의 최적해를 이용하여 순환적으로 큰 문제를 해결한다.
순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다. - DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(Table)에 저장하게 된다.
- 그리고 이렇게 저장된 해들이 다시 필요할 때마다 해를 얻기 위해 다시 문제를 재계산하지 않고, table의 참조를 통해서 중복된 계산을 피하게 된다.
최적 부분 문제 구조
- 동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아니다.
- 주어진 문제가 최적화의 원칙을 만족해야만 동적 계획법을 효율적으로 적용
- 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때, 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다.
- 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 사용할 수 없다.'
분할정복과 DP의 차이
분할 정복
- 연관 없는 부분 문제로 분할한다.
- 부분 문제를 재귀적으로 해결한다.
- 하향식 방법
DP
- 부분 문제들이 연관이 없으면 적용할 수 없다.(즉, 부분 문제들은 더 작은 부분 문제들을 공유한다.)
- 모든 부분 문제를 한번만 계산하고, 결과를 저장하고 재사용한다.(분할 정복은 같은 부분 문제가 나타날 경우 다시 계산한다.)
- 부분 문제들 사이에 의존적 관계가 존재한다.
- 상향식 방법
DP 적용 접근 방법
- 최적해 구조의 특성을 파악하라
문제를 부분 문제로 나눈다. - 최적해의 값을 재귀적으로 정의하라.
부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다. - 상향식 방법으로 최적해의 값을 계산하라.
- 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다.
- 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.(상향식 방법)
package day0410_동적계획법;
import java.util.Scanner;
public class 피보나치 {
static long callFibo1, callFibo2, callFibo3;
static long[] memo;
// static {
// memo = new long[10000];
// memo[0] = 0;
// memo[1] = 1;
//
// //미리 계산을 해놓고
// }
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
memo = new long[N+1]; //0으로 초기화가 되어있다.
// Arrays.fill(memo, -1);
// memo[0] = 0; //위의 코드를 살리면 이 한줄이 필요하다.
memo[1] = 1;
System.out.println(fibo1(N));
System.out.println(callFibo1);
System.out.println(fibo2(N));
System.out.println(callFibo2);
System.out.println(fibo3(N));
System.out.println(callFibo3);
}//main
//재귀 함수를 이용한 피보나치
public static long fibo1(int n) {
callFibo1++;
if(n<2)return n;
return fibo1(n-1)+fibo1(n-2);
}
//memoization 기법을 적용한 피보나치
public static long fibo2(int n) {
callFibo2++;
// if( memo[n] ==-1) { //위의 주석을 풀어버리면 요런게 가넝
if( n>=2 && memo[n] ==0) {
memo[n] = fibo2(n-1)+fibo2(n-2);
}
return memo[n];
}
public static long fibo3(int n) {
callFibo3++;
long[] dp = new long[n+1];
// dp[0] = 0; //이건 필ㄹ요없어
dp[1] = 1;
for(int i = 2; i<=n ; i++) {
dp[i] = dp[i-2] + dp[i-1];
}
return dp[n];
}
}
// 10입력 시
10
55
177
55
19
55
1동전 거스름 돈 구하기
동전의 종류 : 1원,4원,6원
8원을 거슬러 주려고 한다. 최소 몇 개의 동전을 사용해야하나?
package day0410_동적계획법;
import java.util.Scanner;
public class 동전거스름돈 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int money = sc.nextInt(); //해당 돈의 거스름돈의 최소개수를 구하고 싶다.
//사용할 수 있는 동전의 가지수는 3가지로 1원 / 4원 / 6원
int[] dp = new int[money+1];
dp[0] = 0; //굳이 안해도 됨.
// i : 현재 거슬러 주고 싶은 금액
for(int i = 1; i <= money; i++) {
int min = 987654321;
//1원 작은 부분문제에 1원을 추가하는 경우
min = Math.min(min, dp[i-1]+1);
//4원 작은 부분문제에 4원을 추가하는 경우
if(i>=4) min = Math.min(min, dp[i-4]+1);
//6원 작은 부분문제에 6원을 추가하는 경우
if(i>=6) min = Math.min(min, dp[i-6]+1);
dp[i] = min;
}
System.out.println(dp[money]);
}
//메모이제이션으로 해보면 차암 좋겠네... ㅎ
}
//8입력 시
2배낭 문제
10kg 용량의 배낭에 4가지 선물 중 선택해서 넣을 수 있다. 최대 가치가 되도록 선택하면?
package day0410_동적계획법;
import java.util.Scanner;
public class 배낭문제 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//아이템의 개수 N개 / 최대 가방의 무게 W
int N = sc.nextInt();
int W = sc.nextInt();
int[] weights = new int[N+1];
int[] cost = new int[N+1];
for(int i = 1; i<=N; i++) {
weights[i] = sc.nextInt();
cost[i] = sc.nextInt();
}
int[][] dp = new int[N+1][W+1]; //서울6반 고건(매버릭)님 발견
//아이템을 한번도 고려하지 않은경우는 0행에 0으로 초기화가 되어있으니 안할래
//아이템을 한개씩 늘려가면서 고려를 해보자
for(int i = 1; i <=N; i++) {
//각각의 아이템을 이용하여 최적해 갱신
//w : 임시 배낭의 크기
for(int w = 0 ; w<=W; w++) {
if(weights[i] <= w) {
//해당 물건을 넣을지 말지 판단을 해보겠다.
//해당 w의 최적해는 : dp[i-1][w]
//이번 물건을 고려하는 최적해는 : dp[i-1][w-weights[i]]+cost[i]
//위의 두개의 값중 더 좋은걸로 갱신하겠다.
dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weights[i]]+cost[i]);
}else{
dp[i][w] = dp[i-1][w]; //현재 임시무게가 지금 물건을 담을 수 없어서 고려제외
}
}
}
System.out.println(dp[N][W]);
}
}
//
입력
4 10
5 10
4 40
3 50
6 30
출력
90