[ 알고리즘 ] 동적 계획법
@ 왜 궁금한가?
맨날 DP DP 하는데 뭔지 해서,,, 그리고 알고리즘 문제에서 많이 나와서 한번 정리 하고 싶다는 생각,,,
@ 공부
## 동적 계획법이란 ( Dynamic Programming )
- 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결
작은 문제를 해결해서 큰 문제를 해결
> 재귀 호출
def getFibo(n)
if n == 0 or n == 1 :
return 1;
else :
return getFibo(n-1) + getFibo(n-2);문제점: 값을 중복해서 계산 한다.
소문제를 여러번 계산 하는 경우가 많다.
분할정복법을 이용한 풀이가 아님
> 문제를 독립적으로 나누지 않았기 때문
이건 단순히 작은 나를 해결한 결과를 계속해서 써먹는다.
F(n) 을 알기 위해서는 F(n) ~ F(n-1) 을 모두 알아야 함.
"나" 보다 작은 모든 풀이를 먼저 기억하자
어차피 F(n)을 구하기 전에 F(1) ~ F(n-1) 을 먼저 구하자
> 이부분이 분할 정복법 하고 좀 다르다.
> 분할 정복법은 탑 다운 방식 Top Down ( 구해야 할 것을 나눠서 내려간다. )
> Dynamic Programming 은 Buttom up
공통 사항은: 작은 걸로 큰걸 풀자
하지만 철학이 다름
분할 정복법: Top down : 큰 문제를 쪼개 내려가는 것
동적 계획법: Buttom up : 밑에서 올라가는 것
## 동적 계획법의 문제 풀이 순서
1. 부분 문제를 정의 한다. ( 말로 정의 )
- 무슨 값을 구할지를 정의한다.
2. 점화식을 구한다.
- 그 값을 어떻게 구할지에 대한 식을 세운다.
- 부분은 풀려있다고 가정
3. 문제를 해결한다.
- 값을 직접 구하는 코드를 작성한다.
> 0 와 1 은 기저조건 ( Base condition ) 점화식으로 구할 수 없음
## 블럭 채우기
> 부분 문제를 정의 하는 것이 중요하다!!!!!
1. 부분 문제를 정의한다. 무슨 값을 구할지를 정의한다.
> T(i) = 2* i 의 상자를 채우는 경우의 수?
> T(2) = 2
> T(3) = 3
2. 점화식을 구한다. 그 값을 어떻게 구할지에 대한 식을 세운다.
> T(i) =2 *i 의 상자를 채우는 경우의 수
2 * ( i-1) = T(i-1)
2 * (i-2) = T(i-2)
T(i) = T(i-1) + T(i-2)
> 피보나치 수열
## 숫자 만들기
이게 먼저 동적 계획법으로 풀린다라는 감이 잡혀야 한다.
1. 먼저 전체 경우를 생각해 줘야 하고 그 다음에 나눌수 있는지 고려 해야 한다.
5를 만들때 1 2 3 으로만 만드는 경우
13가지 방법
2. 이 전체적인 방법을 어떻게 나눌까?
맨 끝을 주목해서 정렬 하면
5를 만들때
4를 만들어 +1 만 더하면 5가 된다.
3를 만들어 +2만 더하면 5가 된다.
2를 만들어 +3만 더하면 5가 된다.
즉 큰문제를 알기 위해서 작은 문제를 알고 있어야 한다.
## 풀이
1. 부분 문제를 정의한다.
2. 점화식을 구한다.
3. 문제를 해결한다.
하나하나 배열에 넣어 준다.
점화식을 풀기 위해서 T(0) 을 생각해 줘야 한다.
그런데 1~3의 수를 이용하여 0 을 만드는 경우의 수는 뭔가? 말이 안된다. 나머지를 생각해서 배열에 넣게 되면 된다. 단 점화식으로 구할 수 없는 것은 머리로 구해 줘야 한다.
T(0) = x
T(1) = 1
T(2) = 2
T(3) = 4
경우의 수이기 때문에 더하기라고 생각하면 안된다.
T(5) = T(4) +1 +T(3) + 2 + T(2) + 3 이라고 생각하면 안된다. 경우의 수이기 때문에 값을 구하는 것이 아니고 경우를 구하는 것이다. +3 은 5를 만들기 위해서 +3을 했다는 것이지 카운트 하는 것에는 전혀 영향을 안주기 때문에 말이 안되는 수식이다.!!
## 코드
public class DPmakeNumber {
static int MAX = 100;
public static void main(String[] args) {
int[] Table = new int[MAX];
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
Table[1] = 1;
int sum =0;
/*
* M =4
* Table[1] =1
* Table[2] = Table[1] +1
* Table[3] = Table[2]+ Table[1]+1
* Table[4] = Table[3]+Table[2]+ Table[1] +1
*/
for (int i = 2; i <= m; i++) {
sum += Table[i-1];
Table[i] = sum +1;
}
for (int i = m+1; i <= n; i++) {
for(int j=i-m;j<=i-1;j++) {
Table[i] += Table[j];
}
}
System.out.println(Table[n]);
}
}코드는 쉽다 하지만 저기까지의 생각이 도달하기 어렵다.
## 연속 부분 최대합
각각의 경우 오른쪽 끝으로 했을때 그때 가장 큰 값을 구해 본다.
5 : 5
-4 5 : 1
2 -4 5 : 3
1 2 -4 5 : 4
다 더했을 때 5 혼자 있는게 가장 큰 값이 구나 > 동적 계획법을 사용하면 좀 더 빠르게 구할 수 있다.
-4
2 -4
1 2 -4
-4를 끝으로 한 경우에 가장 큰 경우만 생각한다면 3가지 경우 중에서 한가지만 알면 된다.
즉
5
-1 5
이렇게 두가지만 생각하면 된다.
## 풀이
1. 부분 문제를 정의한다.
T(i) = i 번째 숫자를 오른쪽 끝으로 하는 연속 부분 최대합
2. 점화식을 구한다.
즉, 예를 들어
1 2 3 4 5 6 7 8
1, 2, -4, 5, 3, -2, 9, 10 이면 -2을 끝으로 하는 것은
T(5) -2 또는 (-2)
둘중 하나가 되기 때문에
T(i) = max(T(i-1) + Data(i), Data(i) )
3. 문제를 해결한다.
T(0)은 점화식으로 못구한다. 그냥 계산 T(0) = 1
출력시 10일때가 맨 오른쪽일때 가장 최대값을 갖는 구나라고 이야기 할 수 있다.
중간에 최대 값이 나올 수도 있다. 만약에 마지막이 -100 이였다면 25가 아닌 -85가 들어가게 된다. 그럼 10을 오른쪽 끝으로 하는 것이 최대가 아니고 9 가 오른쪽 끝일때가 가장 큰 값이 된다.
즉, 가장 큰 값을 출력 해야 한다. => 그래서 이것이 빠른가?
테이블 채우는데 O(N) 이 걸리게 된다. => 제일 빠르다 그리고 코드가 짧다 !!!
## 구현
public class DP_sumFindMax {
// 1. Table 정의
// 2. 점화식
// Table(i) = i 번째 숫자를 오른쪽 끝으로 하는 연속 부분 최대합
// Table(i) = max( Table(i-1) + Data(i), Data(i))
static int MAX = 100;
public static void main(String[] args) {
int[] Table = new int[MAX];
int[] Data = new int[MAX];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i=0;i<n;i++) {
Data[i] = sc.nextInt();
}
Table[0] = Data[0];
for(int i=1;i<n;i++) {
if(Table[i-1]+Data[i] > Data[i]) {
Table[i] = Table[i-1] + Data[i];
}else {
Table[i] = Data[i];
}
}
int myMax = -9769928;
for (int i = 0; i < n; i++) {
if(Table[i] > myMax) {
myMax = Table[i];
}
}
System.out.println(myMax);
}
}## 팰린드롬 만들기
palindrome이란, 그냥 읽었을 때와 거꾸로 읽었을 때가 같은 문자열이다.
palindrome 을 만들기 위한 최소 추가 문자 개수를 출력하라.
마무리
