DP를 입문하는 가장 대표적인 예시에는 피보나치 수열이 있다
피보나치 수열은 이러한 점화식으로 구성되어있다
n이 1이하일때는 값이 특정되고, 그 보다 클때는 자신의 이전 항들의 값으로 결정이 된다.
-> 피보나치 수열의 경우 바로 전 2개의 항의 값에 영향을 받음
public class Main {
public static void main(String[] args) throws IOException {
System.out.println(fibonacci(4));
}
static int fibonacci(int n){
if(n == 0) return 0;
if(n == 1) return 1;
return fibonacci(n-2) + fibonacci(n-1);
}
}위 코드의 경우에는 n의 값이 30을 넘어서면, 왠만하면 바로 답을 구하지 못하고 실행시간도 n이 증가하면 증가할 수록 기하급수적으로 늘어남
public class Main {
static int[] call = new int[11];
public static void main(String[] args) throws IOException {
System.out.println(fibonacci(10));
for(int i = 0; i < 10; i++){
System.out.printf("fibonacci " + i + "의 호출 횟수 " + call[i] + "\n");
}
}
static int fibonacci(int n){
call[n]++;
if(n == 0) return 0;
if(n == 1) return 1;
return fibonacci(n-2) + fibonacci(n-1);
}
}위 코드를 통해 fibonacci함수의 호출 횟수를 살펴보았을 때
55
fibonacci 0의 호출 횟수 34
fibonacci 1의 호출 횟수 55
fibonacci 2의 호출 횟수 34
fibonacci 3의 호출 횟수 21
fibonacci 4의 호출 횟수 13
fibonacci 5의 호출 횟수 8
fibonacci 6의 호출 횟수 5
fibonacci 7의 호출 횟수 3
fibonacci 8의 호출 횟수 2
fibonacci 9의 호출 횟수 10을 제외하고 n이 작은 함수 호출로 갈수록 호출횟수가 점차 증가됨
그 이유는 프로그램이 실행되는 상황을 그림으로 그려보면 이해하기 쉬움
- f(5)의 값을 수행하기 위해 f(4)와 f(3)의 값을 알아야 함
- 그런데 f(4)의 값을 구할때도 f(3), f(2)의 값을 알아야 하기에, f(4)를 계산해냈을 시점에 우리는 이미 f(3)이 뭔지도 계산을 했음
- 그러나, 뒤에 f(3)을 계산할때 우리가 했던 짓은 다 잊어버리고 다시 계산을 하고 있다.
이를 해결하기 위해 메모이제이션(Memoization)기법을 사용해야 함
public class Main {
static long[] dp;
public static long fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
// 이미 값을 계산한 적이 있다면 그 값을 바로 리턴
if (dp[n] != -1) return dp[n];
// 아니라면 계산해서 dp 배열에 넣어 보존
dp[n] = fibonacci(n - 2) + fibonacci(n - 1);
return dp[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
dp = new long[N+1];
// 초기값 -1은 fibonacci 결과로 절대 나올 수 없는 값
for (int i = 0; i <= N; i++) {
dp[i] = -1;
}
System.out.println(fibonacci(N));
}
}static 배열 dp를 만든 후에, 피보나치 함수에서 절대 나올수 없는 대표적인 값은 -1로 초기화
그리고 피보나치 함수에서 먼저 dp[n]을 계산한 적이 있는지 확인하고(-1이 아닌지 확인), 계산한적이 있다면 추가 재귀 호출 없이 그 값을 바로 리턴
밑의 코드들과 같이 재귀를 사용하지 않고도 풀수있음
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] dp = new int[N + 1];
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
System.out.println(dp[N]);
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] dp = new int[N + 3];
dp[1] = 1;
for (int i = 0; i <= N; i++) {
dp[i + 2] += dp[i];
dp[i + 1] += dp[i];
}
System.out.println(dp[N]);
}
}DP 자체는 주어진 문제를 여러 개의 부분 문제들로 나누어 푼다음, 그 결과들로 주어진 문제를 푼다라고 정의됨
-> 근데 이거 분할 정복도 이랬지않나?
-> 하지만 분할 정복과는 결정적인 차이가있다. 분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션이 필요
이론적인 관점에서 봤을 때 디피는 자신보다 작은 부분 문제 답을 모두 알면 이번 문제를 빨리 풀수있다라는 이야기이고, 실제로 구현하려면 답을 모두 알고 있기 위해 메모이제이션이 필요한 것
-> 둘은 다르긴 하지만 연관성이 깊음
또한 모든 경우를 메모리까지 소비해가며 샅샅이 뒤진다는 점에서 실행시간이 그리디 알고리즘에 비해 떨어지지만, 그리디 알고리즘보다 좀더 폭넓은 범위에서 근사치가 아닌 정확한 값을 얻을수 있다.
기본 문제들과 함께 이해도를 좀더 높여보자!
문제1(실버3)
https://www.acmicpc.net/problem/1463
public class Main {
static int N;
static int[] D;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
D = new int[N+1];
D[1] = 0;
for(int i = 2; i <= N; i++){
D[i] = D[i-1] + 1;
if(i % 2 == 0) D[i] = Math.min(D[i], D[i / 2] + 1);
if(i % 3 == 0) D[i] = Math.min(D[i], D[i / 3] + 1);
}
System.out.println(D[N]);
}
}여기서 D[i]는 i에서 1로 만드는데 걸리는 최소 연산 횟수를 의미
import java.util.*;
public class Main {
static int N;
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
dp = new int[N+1];
Arrays.fill(dp, -1);
System.out.println(solution(N));
}
private static int solution(int n) {
if(n == 1) return 0;
if(dp[n] != -1){
return dp[n];
}
int result = solution(n-1) + 1;
if(n % 2 == 0) result = Math.min(result, solution(n/2)+1);
if(n % 3 == 0) result = Math.min(result, solution(n/3) + 1);
dp[n] = result;
return result;
}
}위와 같이 문제를 푼 경우에는 시간초과가 뜸(탑-다운 방식)
문제2(실버3) : 삼성 기출
https://www.acmicpc.net/problem/14501
못풀었다.. DFS로 푸는것이 쉽기는 함
현재 DP에 대한 개념이 잘 안잡혀 있는 것 같음... 개념을 잘 정립하고 강의들 본 후 이제는 골드 문제들 풀어보자!!!
