DP(Dynamic Programming)
- DP(동적계획법) 이란 어떤 주어진 문제를 작은 문제로 쪼개어 풀어나감에있어 반복되는 호출을 줄이는 방법을 DP라고 부른다.
이 DP를 포스팅한 이유는 '재귀함수' 관련된 피보나치 문제를 풀다가 포스팅을 작성하게 되었다.
알고리즘을 풀며 느끼는것은 나는 재귀함수 부분이 조금 약한거같다. 지난번에 분할정복을 공부하며 더 많이 느끼게되어 더 기억에 잘 남도록 포스팅을 남긴다.
재귀(Top-down)
우선 재귀방식은 우리가 큰 문제를 하위로 쪼개어 가며 문제를 풀어나가는 방식이다. 동적 계획법 또한 같은 방식이지만 큰 차이가 있다 이미 계산한 식은 다시 계산하지 않는다. 즉, 계산된 값을 재활용한다는 뜻이다!
이러한 방식을 메모이제이션 이라고 부른다!
백준 2748
간단하게 아래 문제를 통해 DP 동작 방식을 설명해보겠다.
import java.io.*;
import java.util.*;
public class Main {
public static long[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new long[N + 1];
for (int i = 0; i < N + 1; i++) {
arr[i] = -1;
}
arr[0] = 0;
arr[1] = 1;
System.out.println(solution(N));
}
public static long solution(int N) {
if (arr[N] == -1) {
arr[N] = solution(N - 1) + solution(N - 2);
}
return arr[N];
}
}위 코드를 보면 solution() 함수를 보자 arr[] 을 선언하고 모든 arr[]은 -1로 값을 초기화 한다. 그리고 0, 1은 0과 1로 초기하고 N이 들어와서 arr[N]이 -1이라면 한 번 계산을 해서 arr[N]값을 지정해준다. 만약근데 arr[N]값이 -1이 아닌 이미 존재하는 값이라면 그 값을 반환한다. 이로써 같은 작업을 한 번 만 할 수 있게 된다!
백준 1003
import java.io.*;
import java.util.*;
public class Main {
public static Integer[][] arr = new Integer[41][2]; // 0- 40 / 0, 1
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr[0][0] = 1;
arr[0][1] = 0;
arr[1][0] = 0;
arr[1][1] = 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
solution(num);
sb.append(arr[num][0]).append(" ").append(arr[num][1]).append("\n");
}
System.out.println(sb);
}
public static Integer[] solution(int N) {
if (arr[N][0] == null || arr[N][1] == null) {
arr[N][0] = solution(N - 1)[0] + solution(N - 2)[0];
arr[N][1] = solution(N - 1)[1] + solution(N - 2)[1];
}
return arr[N];
}
}
문제를 풀며 조금 어려워서 다른분들 풀이의 앞부분을 보고 나도 생각해보며 코드를 작성해봤다. 처음에는 어떻게 2748문제처럼 메모이제이션을 활용하여 문제를 풀 수 있을지 생각을 해보았다. 하지만 도무지 생각이 안났는데 2차원 배열을 이용해서 0일때, 1일때를 분리해서 저장해주어야 했다.
그리고 Integer를 쓴 이유는 int[][], long[][] 이런 배열을 선언하면 기본값이 null 이 아니다. 그냥 0이 저장된다. 하지만 Integer로 만들게되면 null로 초기 선언이 된다. 그렇기때문에 int, long으로 선언하면 -1로 초기화를 해주어야하는데 (기본값이 0이면 횟수로 생각해버릴수있기때문에.) Integer로 선언하면 null이기 떄문에 위처럼 체크해주면 된다.
이렇게 각 1, 0 일때 호출 횟수를 메모이제이션을 활용해서 저장하면 문제를 풀 수 있다. 확실히 이렇게 문제를 기본, 응용 푸니까 좀 더 이해가 잘 됐다.
