TIL
동적 프로그래밍 관련 문제를 풀어보았다.
동적 프로그래밍(Dynamic Programming)
재귀 함수를 이용하여 문제를 풀면 같은 계산을 반복하게 되어 너무 많은 계산 시간을 소비하게 되는 경우가 있다.
대표적인 예가 피보나치 함수
그림에서 보면 F5부터 2번 이상씩 중복해서 나타나는 것을 알 수 있다.
이렇게 중복으로 나타나는 값들을 따로 저장해 두고, 필요할 때 꺼내쓰면 다시 계산하는 시간을 줄일 수 있다. 부분결과를 저장하면서 해를 구해나가는 것, 이것이 동적 프로그래밍의 핵심이다.
다음 두 성질이 있는 문제에 대해 적절한 저장 방법으로 중복 호출의 비효율을 제거한 것을 동적 프로그래밍이라 한다.
- 최적 부분 구조를 이룬다.
- 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.
구현 방법은 배열 n[][] 을 만들고 작은 것 부터 하나하나 값을 채워 넣어 가면 된다.
값을 채워 넣고 반복문을 돌릴 때 필요한 값을 배열에서 가져오면 된다.
(동적 프로그래밍이란 용어는 원래 제어 분야에서 해를 테이블에 저장해가면서 풀어나간다는 데에서 유래했다고 한다. 이 기법의 내용을 놓고 보면 딱히 어울리지도 않고 직관적인 이해에도 도움이 되지 않는다. 그냥 옛날부터 이렇게 불러왔으니 이렇게 말하는 것..)
백준 9184번: 신나는 함수 실행
안신난다
https://www.acmicpc.net/problem/9184
문제에 나와있는 함수 그대로 구현하면 당연~히 시간초과가 나겠지..
동적 프로그래밍으로 구현한다.
함수를 잘 보면
- if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1
- if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)
조건이 있다.
a나 b나 c가 하나라도 0이거나 0보다 작으면 1을 반환,
하나라도 20보다 크면 w(20,20,20) 을 반환한다.
a, b, c의 범위가 -50< a, b, c < 50 이여도 반환 값은 1<= w(a, b, c) <= w(20,20,20) 사이 라는 것이다..
동적 프로그래밍으로 이를 구현할 때 먼저 배열을 선언 하는데
크기를 50..이렇게 할게 아니고 21만 해둬도 된다.
0이거나 0보다 작은 숫자가 오면 [0][0][0]에 저장된 값을, 20보다 큰 수가 오면 [20][20][20]을 반환하면 된다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class fun_ction_9184 {
static int[][][] dp = new int[21][21][21];
static int w(int a,int b,int c) {
if(inRange(a, b, c) && dp[a][b][c] != 0) {
return dp[a][b][c];
}
if(a<=0 || b<=0 || c<=0) {
return 1;
}
if(a>20||b>20||c>20) {
return dp[20][20][20]= w(20,20,20);
}
if(a<b && b<c) {
return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
}
return dp[a][b][c]= w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while(true) {
StringTokenizer st= new StringTokenizer(br.readLine());
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
int c=Integer.parseInt(st.nextToken());
if(a==-1&&b==-1&&c==-1) {
break;
} // 모두 -1일 때 break한다.
int result=w(a,b,c);
bw.write("w("+a+", "+b+", "+c+") = "+result+"\n");
}
bw.flush();
bw.close();
}
static boolean inRange(int a,int b,int c) {
return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20;
}
}
또 0<= a,b,c <=20 을 벗어나는 값이 들어오면 오류가 날 수 있기 때문에 이로 인한 오류를 방지하도록 처리해준다. (inRange 함수)
한창 알고리즘 수업을 들을 때 이게 무슨 말인지 몰랐는데 다시 공부하니 좀 감이 생기는 것 같다.
앞으로도 열공!
