시작하기 전...
Dynamic Programming
DP(Dynamic Programming)는 복잡한 문제를 간단한 여러 개의 문제로 나눠 푸는 방법을 말한다.
나무위키에 정의된 글을 보면, "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘이라고 나온다.
동적 계획법을 적용시킬 수 있는 예중에 하나가 피보나치 수이다.
피보나치 수
수학에서 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미한다.
(편의상 0번째 항을 0으로 두기도 한다.)
피보나치 수 정의
피보나치 수 F(n)는 다음과 같은 초기값 및 점화식으로 정의되는 수열이다.
F(1) = F(2) = 1
F(n) = F(n-1) + F(n-2)
0번째 항부터 시작할 경우
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
요약하자면....
피보나치 수열은 수학적으로 간단하지만, 프로그래밍적으로 최적화를 요구하는 대표적인 문제이다.
이번 글에서는 Java를 사용하여 동적 계획법(DP)을 활용한 효율적인 피보나치 수열 계산 방법을 소개할 예정이다.
백준 2747 -피보나치 수바로가기
📝 문제 설명
-
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
Fn = F(n-1) + F(n-2) (n ≥ 2) n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
- n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하라.
입력
첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.
출력
첫째 줄에 n번째 피보나치 수를 출력한다
입출력 예시
📌 풀이 1) 단순 재귀 방식
피보나치만 보고 문제를 풀면 단순 재귀함수로 풀면 될거라 생각할것이다.
(.....그게 바로 저에요.)
재귀함수로만 푼 코드를 살펴보면 아래와 같다.
int num = 10;
System.out.print(fibonacci(num));
-----------------------------------------------------------
public static int fibonacci(int i) {
if (i <= 1) {
return i; // F(0) = 0, F(1) = 1
}
return fibonacci(i - 1) + fibonacci(i - 2);
}이렇게 풀면 틀렸다고 나오죠? 왜냐
🚨 단순 재귀 방식의 문제점 🚨
중복계산
예를 들어 F(5)를 계산할 때 𝐹(4)+𝐹(3)을 계산한다.
하지만 F(4)를 계산하기 위해 다시 F(3)+F(2)를 계산하는데,
F(3)은중복적으로 계산된다.
// 위 글을 시각화한 트리
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \
F(2) F(1)
F(3)은 2번, F(2)는 3번 계산된다.
위와 같은 방식으로 계산하면 F(3)이 두 번, F(2)가 세 번, F(1)이 여러 번 호출되는 비효율적인 방식인걸 알 수 있는데, 이때 시간 복잡도가 O(2^n) 에 달하게 되며, n 이 커질수록 계산 속도가 매우 느려진다.
🚨 문제 해결 방법 🚨
이러한 문제를 해결하려면 동적 계획법(DP) 을 사용하여 이미 계산된 값을 저장하고 재사용하는 방법이 필요하다.
| 방식 | 시간복잡도 | 공간 복잡도 | 특징 |
|---|---|---|---|
| 단순 재귀 | O(2^n) | O(N) | 중복 계산이 많아 성능이 매우 비효율적 |
| DP | O(N) | O(N) | 중복 계산을 방지하여 효율적 |
📌 풀이 2) DP 방식
이전에 계산된 값을 배열에 저장해 두고, 필요할 때 다시 사용하는 방식으로 풀어보자
public class Main {
static int[] dp; // DP 배열 선언
public static void main(String[] args) {
int num = 10; // 계산할 피보나치 수의 인덱스 설정
dp = new int[num + 1]; // DP 배열 초기화 (0부터 num까지 포함)
System.out.print(fibonacci(num)); // 피보나치 수 출력
}
public static int fibonacci(int i) {
if (i <= 1) {
return i; // 기저 조건: F(0) = 0, F(1) = 1
}
if (dp[i] != 0) {
return dp[i]; // 이미 계산된 값이 있으면 바로 반환
}
dp[i] = fibonacci(i - 1) + fibonacci(i - 2); // 점화식: F(n) = F(n-1) + F(n-2)
return dp[i];
}
}
📚 코드 설명
1️⃣ 입력 처리
사용자로부터 num 값을 입력받아 처리
num은 1 ≤ num ≤ 45로 제한
(입출력 예시로 10으로 초기화 설정함)
2️⃣ 동적 계획법 배열 초기화
dp 배열은 이전에 계산한 값을 저장하기 위해 사용
dp[i]는 F(i) 값을 저장
3️⃣ 피보나치 계산 로직
- 기저 조건
F(0)=0, F(1)=1로 설정 - 중복 계산 방지
이미 계산된 값은 dp[i]에서 바로 반환 - 점화식 적용
계산되지 않은 경우, F(n)=F(n−1)+F(n−2)로 값을 계산하고 dp[i]에 저장
🧠 시간 및 공간 복잡도 분석
시간 복잡도
- 각 F(i)는 한 번만 계산되므로 시간 복잡도는 O(n) 이다.
공간 복잡도
- 추가로 사용하는
dp배열은 O(n) 의 공간을 차지한다.
전체코드 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
dp = new int[num + 1];
System.out.print(fibonacci(num));
}
public static int fibonacci(int i) {
if (i <= 1) {
return i;
}
if (dp[i] != 0) {
return dp[i];
}
dp[i] = fibonacci(i-1) + fibonacci(i-2);
return dp[i];
}
}전체코드 2 (수정 ver)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
int num = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
int[] dp = new int[num + 1];
System.out.print(fibonacci(num, dp));
}
private static int fibonacci(int i, int[] dp) {
if (i <= 1) return i;
if (dp[i] == 0) dp[i] = fibonacci(i - 1, dp) + fibonacci(i - 2, dp);
return dp[i];
}
}