Java - 동적 프로그래밍(DP, Dynamic Programming)

◎동적 계획법, 다이나믹 프로그래밍(DP, Dynamic Programming)

 

분할정복 기법(큰 문제를 작은 문제로 나누어 푸는 방법)을 사용할때, 반복되는 문제의 답을 기록해 둠으로서 그 문제들을 재계산하지 않고 재사용하는 방법. Dynamic(동적)과 Programming(계획법)이라는 뜻과는 전혀 상관없다.

 

1. 최적 부분 구조(Optimal Substructure):

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다

 

2. 중복되는 부분 문제 (Overlapping Subproblem):

동일한 작은 문제를 반복적으로 해결해야 한다

 

의 두가지 조건을 만족할때 사용할 수 있다.

 

---

◎ DP 문제 예시-1, 피보나치 수열

 

 

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

Fn = Fn-1 + Fn-2 (n ≥ 2)이므로, Fn-1과 Fn-2의 값을 어딘가에 저장해두고 Fn을 구할때, 저장해둔 Fn-1과 Fn-2을 쓰는 것이 DP적인 활용이다.

 

코드:

package dynamic_algorithm;

import java.util.ArrayList;

public class Fibonacci_Numbers {
	
	ArrayList<Integer> arr; //피보나치 수열을 저장한 배열
	int num;//출력할 개수
	
	Fibonacci_Numbers(int num){
		this.num = num;
		arr = new ArrayList<>();
		
		arr.add(0);
		arr.add(1);
		//피보나치 수열 생성
		for(int i=2; i<this.num; i++) {
       		// Fn = Fn-1 + Fn-2 (n ≥ 2)
			arr.add(arr.get(i-1) + arr.get(i-2));
		}
		
		//피보나치 수열 출력
		for(int i=0; i<this.num; i++) {
			System.out.print(arr.get(i));
			System.out.print(" ");
		}
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Fibonacci_Numbers(10);
	}

}

실행 결과:

0 1 1 2 3 5 8 13 21 34 

---

◎ DP 문제 예시-2, 막대기 자르기

 

길이(i)	0	1	2	3	4	5	6	7	8	9	10
가격(Pi)	0	1	5	8	9	10	17	17	20	24	30

위의 표는 막대기와 그 길이에 따른 가격이다.

길이가 4인 막대기를 그냥 팔면 가격이 9이지만, 2와 2로나누어 팔면 5+5 = 10 이다.

 

이를 점화식으로 나타내면 길이가 n인 막대기의 최대 가격 Rn= max(Pi + Rn -i) (i는 1부터 n)이다.

길이가 0인 막대기의 최대 가격은 Max(P0) = 0

길이가 1인 막대기의 최대 가격은 Max(P1 + R0) = 1

길이가 2인 막대기의 최대 가격은 Max(P2 + R0, P1 + R1) = Max(5, 2) = 5

길이가 3인 막대기의 최대 가격은 Max(P3 + R0, P2 + R1, P1 + R2) = Max(8,6,6) = 8

길이가 4인 막대기의 최대 가격은 Max(P4 + R0, P3 + R1, P2 + R2, P1 + R3) = Max(9,9,10,9) = 10

 

Rn이 계속해서 나오므로, 이 값들은 배열에 저장하고 가져다 쓰면, 매번 Rn을 구하는 계산을 하지 않아도 된다.

 

코드:

package dynamic_algorithm;

import java.util.ArrayList;
import java.lang.Math;

public class cutting_pole {
	
	private static int cutpole(int[]value, int length) {
		
		//Rn을 저장하는 ArrayList
		ArrayList<Integer> max_value = new ArrayList<Integer>();
		
		//R0 = 0
		max_value.add(0);
		
		//Rn= max(Pi + Rn -i) (i는 1부터 n)
		for(int i = 1; i<=length; i++) {
			int q = -1;
			for(int j = 1; j<=i; j++) {
				q = Math.max(q, value[j] + max_value.get(i-j));
			}
			max_value.add(q);
		}
		
		return max_value.get(length);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] value = {0,1,5,8,9,10,17,17,20,24,30};
		
		System.out.println(cutpole(value,2));
		System.out.println(cutpole(value,3));
		System.out.println(cutpole(value,4));
		System.out.println(cutpole(value,7));
		
	}

}

실행결과

5
8
10
18

---

◎ DP 문제 예시-3, 최장 공통 부분 수열(LCS) 문제

 

-공통 부분 문자열(Longest Common Substring) / 공통 부분 수열(Longest Common Subsequence)

 

출처:https://mygumi.tistory.com/126 

공통 부분 문자열은 공통된 문자열이 계속에서 이어져야하므로, 최장 공통 문자열의 길이는 3이다.

공통 부분 문자열은 수열이 계속 이어질 필요없이 순서만 맞으면 되므로, 최장 공통 부분 수열의 길이는 5이다.

 

1. 맨 마지막 문자가 같다면, LCS는 맨 마지막 문자를 지운 두 문자열의 LCS +1 이다.

ex. LCS("ABBA","BAAA") = 1 + LCS("ABB","BAA") ;

 

맨 마지막 문자가 다르다면, LCS는 각각의 문자열에서 맨 마지막 문자를 지운 경우 중 최대값이다.

ex. LCS("ABB","BAA")  = Max( LCS("AB","BAA"), LCS("ABB","BA"));

 

2. 구현을 쉽게 하기 위해서 문자열의 길이보다 1이긴 이차원 배열을 설정한다.

문자열의 길이가 1인경우, 문자열을 삭제하게 되면 남는 문자열이 없으므로, 문자열의 길이보다 1이긴 이차원 배열을 설정하고 0으로 채워주어 , 따로 문자열의 길이가 1인 경우를 처리하지 않도록한다.

 

코드:

package dynamic_algorithm;

import java.lang.Math;

public class Longest_Common_Subsequence {

	private static int lcs(String a, String b) {
		
		StringBuffer A = new StringBuffer(a); 
		StringBuffer B = new StringBuffer(b);
		
		/*
		 * 구현을 쉽게 하기 위해서 문자열의 길이보다
		 * 1이긴 이차원 배열을 설정한다.
		 */ 
		int[][] mem = new int[A.length()+1][B.length()+1];
		
		for(int i = 1; i<=A.length(); i++) {
			for(int j = 1; j<=B.length(); j++) {
				//맨 마지막 문자가 같다면, 
				//LCS는 맨 마지막 문자를 지운 두 문자열의 LCS +1 이다.
				if(A.charAt(i-1)==B.charAt(j-1)) {
					mem[i][j] = 1 + mem[i-1][j-1];
				}
				//맨 마지막 문자가 다르다면,
				//LCS는 각각의 문자열에서 맨 마지막 문자를 지운 경우 중 최대값이다.
				else {
					mem[i][j] = Math.max(mem[i][j-1],mem[i-1][j]);
				}
			}
		}
		
		
		return mem[A.length()][B.length()];
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		System.out.println(lcs("ABCBDAB", "BDCABA"));
	}

}

 

실행 결과:

4

---

 

◎ DP 문제 예시-4, 0/1 배낭 문제

 

	0	10	20	30	40	50
0	0	0	0	0	0	0
1	0
2	0
3	0

 

무게제한이 0이거나, 들어가는 보석의 수가 0인 경우 가치는 0이다.

 

1. 1번 보석까지 배낭에 넣을 수 있다

	0	10	20	30	40	50
0	0	0	0	0	0	0
1	0	10	10	10	10	10
2	0
3	0

 

2. 2번 보석까지 배낭에 넣을 수 있다.

	0	10	20	30	40	50
0	0	0	0	0	0	0
1	0	60	60	60	60	60
2	0	60	100	160	160	160
3	0

무게제한 20에서는 10짜리 보석 한개를 넣는 가치(60)보다, 20짜리 보석을 넣는 가치(100)이 더 크므로 20짜리 보석을 넣었다.

무게제한 30에서는 10짜리 보석 한개를 넣는 가치(60)보다, 20짜리 보석을 넣는 가치(100) + 남는 공간 10에 10짜리 보석을 넣는 가치(60) 가 더 크므로 20짜리 보석을 넣었다.

 

 

3. 3번 보석까지 배낭에 넣을 수 있다.

	0	10	20	30	40	50
0	0	0	0	0	0	0
1	0	60	60	60	60	60
2	0	60	100	160	160	160
3	0	60	100	120	180	220

무게제한 50에서는 (50,2)에 위치한 가치 160보다 30짜리 보석의 가치(120) + 남는 공간 20의 가치((20,2)에 위치한 가치)가 더 크므로 총 가치는 220이다.

 

코드:

package dynamic_algorithm;

public class Zero_One_Knapsack {

	static int find_Knapsack(int[] weight, int[] value, int limit) {

		//무게 제한에 따른 최대가치를 나타내는 table배열
		/*
		 * 구현을 쉽게 하기 위해서 가치 배열의 길이, 무게제한의 크기보다
		 * 1이 긴 이차원 배열을 설정한다.
		 */ 
		int[][] table = new int[value.length+1][limit +1];
		
		
		for(int i = 0; i<value.length+1; i++) {
			for(int j = 0; j<limit+1; j++) {
				//배낭이 없거나, 무게제한이 0이면 아무것도 들어갈 수 없으므로 0
				if(i==0 ||j==0){
					table[i][j] = 0;
					continue;
				}
				//무게제한보다 무게가 크면, 넣을수 없다
				if(weight[i-1]>j) {
					table[i][j] =  table[i-1][j];
				}
				//무게 제한보다 무게가 작다면, 공간을 확보하고 보석을 넣는 경우와, 넣지 않는 경우를
				//비교하여 최댓값을 취한다.
				else {
					table[i][j] = Math.max(value[i-1] + table[i-1][j-weight[i-1]],table[i-1][j] );
				}
			}
		}
		
		return table[value.length][limit];
		
	}
		
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] weight = { 10,20,30 };
		int[] value = { 60,100,120 };
		
		System.out.println(find_Knapsack(weight, value, 50));
		}
}

 

실행 결과:

220

---

어떤 문제가 DP로 풀리는지 어떤 계산이 반복되는지, 경험이 아직 많이 부족하여 잘 보이지가 않는다. DP에 관한 많은 문제를 풀어봐야겠다.

 

---

◎ Git codes:

https://github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/dynamic_algorithm