다이나믹 프로그래밍 (DP)
해당 문제의 알고리즘을 확인해보면 '다이나믹 프로그래밍' 이라고 되어 있다.
이는 동적 계획법이라고도 불리며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.
이는 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용하는 방식으로 자주 쓰인다. (기억해가면서 풀기)
DP를 쓰는 이유
일반적인 재귀 방식 또한 DP와 매우 유사하다.
하지만 둘의 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.
예를 들어 피보나치 수열을 살펴보자.
피보나치 수열은 다음과 같다.
1, 1, 2, 3, 5, 8, 13, 21, 34, ,,,,
피보나치 수열을 구하고 싶을 때 재귀함수로 구현하면 어떻게 될까?
단순하게 return f(n) = f(n-1) + f(n-2) 로 구현 할 수 있다.
그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다.
왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문이다.
그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 어떨까? 앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능해진다.
즉, 매우 효율적으로 문제를 해결할 수 있게 된다. 시간복잡도를 기준으로 아래와 같이 개선이 가능하다.
O(n^2) → O(f(n)) 로 개선 (다항식 수준으로, 문제에 따라 다름.)
출처 : https://hongjw1938.tistory.com/47
9095번 풀이
다이나믹 프로그래밍의 개념을 고려하면서, 9095번 문제를 풀어보자.
문제 : https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
arr[n] 1차원 배열 을 생성한다. arr[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다.
n=1일때
1
-> arr[1]=1
n=2일때
1 + 1
2
->arr[2]=2
n=3일때,
1 + 1 + 1
1 + 2
2 + 1
3
->arr[3] = 4
n=4일때,
1 + 1 + 1 + 1
1 + 2 + 1
2 + 1 + 1
3 + 1
1 +1 + 2
2 + 2
1 + 3
-> arr[4] = 7
n=4일때를 체크해보면, arr[4] = arr[3] + arr[2] + arr[1] 임을 알 수 있고,
이를 통해 arr[n] = arr[n-1] + arr[n-2] + arr[n-3] 이라는 점화식을 이끌어 낼 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int [] arr = new int[11];
// 배열 arr의 초기값 세팅
arr[1]=1;
arr[2]=2;
arr[3]=4;
// 점화식을 이용해 배열에 값 채우기
for (int i=4;i<11;i++){
arr[i] = arr[i-3]+arr[i-2]+arr[i-1];
}
for (int i=0;i<T;i++){
int n = Integer.parseInt(br.readLine());
System.out.println(arr[n]);
}
}
}