[1일1커밋 10D] 유형별(3) DP 동적프로그래밍 | 백준 JAVA

[BAEKJOON 백준] 문제 > 단계별풀이 > 동적 계획법 1 https://www.acmicpc.net/step/16

 

* Dynamic Programming (동적프로그래밍, 동적계획법, DP)

큰 문제를 작은 문제로 나누어 해결하는 기법으로, 작은 부분 문제들이 반복되는 점을 이용하여 풀어나가는 방법이다.

모든 작은 문제들은 한번만 풀고 어디엔가 기억해둔다. 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 기억한 값을 활용한다.

• Bottom-Up : 작은 문제부터 해결해나간다.
• Top-Down : 주로 재귀로 푸는 형태가 이 경우에 해당한다.

DP는 하나의 문제를 단 한번만 푸는 반면, 분할 정복 기법(Divide and Conquer)은 동일한 문제를 다시 푼다는 단점이 있다.
분할정복은 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법으로 작은 문제의 반복이 일어나지 않는다.

 

 

24416. 알고리즘 수업 - 피보나치 수 1 (브론즈1) https://www.acmicpc.net/problem/24416

import java.io.*;

public class Main {

	static int cnt1=0, cnt2=0;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		fib(n);
		int[] dp = new int[n+1];
		fibonacci(dp, n);
		System.out.println(cnt1 +" "+cnt2);
	}
	
	// 재귀호출 
	static int fib (int n) {
		if(n==1 || n==2) {
			cnt1++;
			return 1;
		}
		else {
			return (fib(n-1)*fib(n-2));
		}
	}
	
	// 동적 프로그래밍
	static int fibonacci(int[] dp, int n) {
		dp[1]=1;
		dp[2]=1;
		for(int i=3; i<=n; i++) {
			cnt2++;
			dp[i] = dp[i-1]+dp[i-2];
		}
		return dp[n];
	}
}

의사코드가 주어져서 어렵지 않았음 재귀와 동적 프로그래밍 알고리즘이 어떤식인지 비교하기 좋았던 문제

 

9184. 신나는 함수 싫애 (실버2) https://www.acmicpc.net/problem/9184

처음에 뭘 하라는건지 이해가 안되어서 헤맸었다.

import java.io.*;
import java.util.*;

public class Main {

	static int[][][] dp = new int[21][21][21];
	public static void main(String[] args) throws Exception{
		int a, b, c;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		while(true) {
			st = new StringTokenizer(br.readLine(), " ");
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());

			if(a == -1 && b == -1 && c == -1) break;
			long result = dynamicW(a,b,c);
			sb.append("w("+a+", "+b+", "+c+") = "+result+"\n");
		}
		
		System.out.println(sb);
		br.close();
	}
	
	static int w(int a, int b, int c) {
		if(a<=0 || b<=0 || c<=0) return 1;
		if(a>20 || b>20 || c>20) return w(20, 20, 20);
		if(a<b && b<c) return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
		return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
	}
	
	static int dynamicW(int a, int b, int c) {
		if(a<=0 || b<=0 || c<=0) return 1;
		if(a>20 || b>20 || c>20) return dynamicW(20, 20, 20);
		if(dp[a][b][c] > 0) return dp[a][b][c]; // 저장된 값이 있을 경우 
		if(a<b && b<c) {
			dp[a][b][c] = dynamicW(a, b, c-1) + dynamicW(a, b-1, c-1) - dynamicW(a, b-1, c);
			return dp[a][b][c];
		}
		dp[a][b][c] = dynamicW(a-1, b, c) + dynamicW(a-1, b-1, c) + dynamicW(a-1, b, c-1) - dynamicW(a-1, b-1, c-1);
		return dp[a][b][c];
	}
}

의사코드로 주어진 함수에 DP를 위해 몇 코드를 추가하여 완성시키는 그런 문제였던거같다. DP 이해를 돕기 위해

어쩌라는건지 몰라 대충 끌적이다 구글링해봄. DP의 핵심은 작은 문제들을 배열에 저장하는 것이다. 따라서 배열 선언 후 값들을 계산 및 저장하고 조건에 따라 리턴하도록 추가했다. 

나처럼 궁금한 사람이 있더라 → 이거 무슨 문제죠?? .. https://www.acmicpc.net/board/view/150588

나에게는 도움이 되지 못한 DP 개념 문제...ㅠ

 

1904. 01타일 (실버3) https://www.acmicpc.net/problem/1904

풀다 말았던..