Dynamic Programming
개념
- 특정 규칙(점화식)을 찾아내서 적용한다. -> 재사용성
- 구간의 값을 배열을 이용하여 저장
-> memoization : 동일 구간 계산시 이용- Top down 방식, Bottom up 방식 2가지가 존재
DP 문제를 알아내는 방법
1. 각 구간에서 규칙이 동일한 값을 찾아낸다.
-> ex) f[i] = f[i-1] + f[i-2]
2. dp 배열을 만들어서 Bottom Up 방식으로 해당 공식을 접근한다.
Sapmle (Fibonacci Number - 피보나치 수)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
f(2) = f(1) + f(0)
-> f(i) = f(i-1) + f(i-2)f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2) (n > 1)
Input : n = 3
Output : 2
설명) f(3) = f(2) + f(1) = 1 + 1 = 2
피보나치 수를 구할 때 f(i-1), f(i-2)에 해당하는 부분이 중복되어 호출된다. 따라서 수가 커지면 커질수록 값을 구하는 시간이 길어질 수밖에 없어서 DP를 이용해야한다.
기본 코드
public class Fibo {
public static void main(String[] args) {
int n = 7;
System.out.println(fibonacci(n));
}
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 2) + fibonacci(n - 1);
}
}
}Top Down 방식
public class Fibo {
// 길이 1000으로 가정
public static int[] dp = new int[1000];
public static void main(String[] args) {
int n = 7;
System.out.println(fibonacci(n));
}
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
if (dp[n] != 0) {
return dp[n];
}
dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
return dp[n];
}
}Bottom UP 방식
public class Fibo {
// 길이 1000으로 가정
public static int[] dp = new int[1000];
public static void main(String[] args) {
int n = 7;
System.out.println(fibonacci(n));
}
public static int fibonacci(int n) {
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}문제
1. DP - House Robber
인접한 두 집에 침입하면 경찰에 자동으로 연락된다. 각 House의 금액은 자연수로 주어지며 경찰에 걸리지 않고 오늘 밤 도둑질 할 수 있는 최대 금액은 얼마인가?
Input : int[] nums = [2,7,9,3,1,8]
Output : 19
풀이
DP 문제인지 알아내는 방법
1. 이미 셋팅 된 값에서 규칙을 찾는다.
-> 새로운 어떤 값을 찾는 것이 아님
2. 2번방을 기준으로 잡는다.
3. 2번방은 11이 나와야 함 11 = max(7, (2+9))
즉, DP 배열은 해당 위치까지의 누적된 최대 금액을 저장하는 것이다. DP 배열을 주어진 nums길이의 +1 크기 만큼 선언한다.
nums[2] 를 기준으로 예를 들어보면 nums[2]부분일 때 nums[0]을 털고 nums[2]를 터는 방법과 nums[1]를 터는 방법 2개가 존재한다. 이 2개중에 최대값을 dp[i+1]에 저장하면 되는 것이다. dp배열에는 [0, 2, 7, 11, 11, 12, 19]가 들어가게 된다.
즉 dp[i+1] = Math.max(dp[i], dp[i-1] + val)라는 식을 구할 수 있다.
소스
public class Q1 {
public static void main(String[] args) {
int[] nums = { 2, 7, 9, 3, 1, 8 };
System.out.println(solve(nums));
}
public static int solve(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 1; i < nums.length; i++) {
int val = nums[i];
dp[i + 1] = Math.max(dp[i], dp[i - 1] + val);
}
return dp[nums.length];
}
}2. DP
'A' : "1" , 'B' : "2" ... 'Z' : "26"이라 했을 때 나올 수 있는 문자열의 갯수를 구해라
Input : String s = "12"
Output : 2
설명) "1", "2" : AB , "12" : L
Input : String s = "121"
Output : 3
Input : String s = "3621"
Output : 2
풀이
- 한 자리씩 증가시키면서 만들 수 있는 문자열의 갯수를 저장하는 dp 배열을 만든다.
-> dp배열의 길이는 문자열 길이의 + 1이다. - 규칙을 찾아내어 Bottom Up 방식으로 찾아낸다.
- 알파벳이 최대 26까지이기 때문에 두자리씩 파악해야 한다.
ex) "121" 일 때
dp[0] = 1 이고 dp[1] = 1이다. (1,2,1 -> "ABA")
dp[2]에서는 "121"에서 앞에 "12"를 기준으로 "2" -> B "12" -> L 따라서 dp[2] = 2
여기서 확인할 수 있는 규칙은 dp[i] = dp[i-1] + dp[i-2] 라는 것을 알 수 있다.
소스
public class Q2 {
public static void main(String[] args) {
String s = "121";
System.out.println(solve(s));
}
public static int solve(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; i++) {
int first = Integer.valueOf(s.substring(i - 1, i));
int second = Integer.valueOf(s.substring(i - 2, i));
//System.out.println("i " + i + " first: " + first + " second " + second);
if (first >= 1 && first <= 9) {
dp[i] += dp[i - 1];
}
if (second >= 10 && second <= 26) {
dp[i] += dp[i - 2];
}
//System.out.println("dp : " + dp[i]);
}
return dp[n];
}
}참고
인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디
