오늘은 백준에서 피보나치 함수라는 것을 풀었습니다.
문제
일단 피보나치 함수는 자료구조에서 순환을 배울때 자주 등장하는 공식입니다.
그런데 여기서 DP(다이나믹 프로그래밍)라는 알고리즘 사용해야됩니다.
문제 개념 자체는 쉽습니다. fibo(3) 라는 피보나치 공식이 돌아가면 여기서 0, 1이 몇번 나오는지 확인하는 문제입니다. 하지만 저는 DP 문제를 거의 풀어보지 않고 개념도 잘 몰라서 30분 정도 생각후 그냥 답지를 보았습니다.
DP(Dynamic Programming)
한국어로 동적 계획법이라고도 읽습니다. 하지만 저는 DP알고리즘의 개념을 알게 된 후 기억 알고리즘, 메모하는 알고리즘이라는 말이 뭔가 더 맞는거 갑습니다.
일단 이 문제는 최대 40까지의 피보나치가 들어갈 수 있습니다. 만약 3이라는 피보나치를 구현 한다고 해봅시다.
그러면 피보나치 fibo(3) -> fibo(2) -> fibo(1)이라는 재귀를 돌아야 됩니다.
이렇게 되면 N^2만큼 돌게 됩니다. 하지만 문제 시간제한을 보면 0.25초 라는 시간을 줍니다.
이렇게 되면 40이라는 피보나치가 돌게 되면 102334155이라는 값이 나오게되는데 그럼 만큼 2제곱이되면 말도 안되는 시간이 걸립니다. 여기서 DP 알고리즘을 사용하면 빠르게 값을 구할 수 있습니다.
하지만 조건이 있습니다. DP 알고리즘을 쓸러면 항상 값이 일정해야 됩니다.
그런데 피보나치는 이 조건에 해당됩니다. 1을 넣으면 1이 나오고 8을 넣으면 항상 21이 나옵니다. 이 값은 바뀌지 않고 일정합니다.
여기서 이제 이 알고리즘의 핵심입니다. 값이 일정한 경우 어딘가에 기록을 하고 다시 재사용하자!
좀 더 있어보이게 얘기하면 메모리 사용량을 늘리고 실행시간을 낮춥니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Day01_피보나치함수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int[] fibo0 = new int[41];
int[] fibo1 = new int[41];
fibo0[0] = 1;
fibo0[1] = 0;
fibo1[0] = 0;
fibo1[1] = 1;
int a = Integer.parseInt(br.readLine());
for (int j = 2; j <= a; j++) {
fibo0[j] = fibo0[j - 1] + fibo0[j - 2];
fibo1[j] = fibo1[j - 1] + fibo1[j - 2];
}
System.out.println(fibo0[a] + " " + fibo1[a]);
}
}
}이 코드는 자료구조 순환에서 보았던 피보나치와는 많이 다르게 생겼습니다.
우리가 보았던 피보나치는
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}이렇게 생겼기 때문입니다. 그럼 다시 설명하겠습니다.
for (int i = 0; i < t; i++) {
int[] fibo0 = new int[41];
int[] fibo1 = new int[41];
fibo0[0] = 1;
fibo0[1] = 0;
fibo1[0] = 0;
fibo1[1] = 1;
int a = Integer.parseInt(br.readLine());
for (int j = 2; j <= a; j++) {
fibo0[j] = fibo0[j - 1] + fibo0[j - 2];
fibo0[j] = fibo1[j - 1] + fibo1[j - 2];
}
System.out.println(fibo0[a] + " " + fibo1[a]);
}먼저 40까지의 피보나치가 문제에서 제안을 했기 때문에 40개의 값을 넣을 수 있는 배열 두개를 선언합니다.
그리고 fibi0 첫번째에는 1을 넣고 두번째는 0을 넣습니다. 그리고 fibo1에는 0을 처음에넣고 1을 두번째에 넣습니다.
예를 들어 이제 피보나치 1을 들어가면 1은 한번 0은 0번 등장했기 때문에 0, 1이 출력 되어야 됩니다.
이것을 미리 값을 넣어줍니다.
0을 담당하는 배열을 먼저 보면
fibo0[0] = 1;
fibo0[1] = 0;어차피 0은 무조건 한번 등장하기 때문에 1번, 1은 없기 때문에 0번
1을 담당하는 배열도 똑같습니다.
피보나치 5를 0,1의 등장 횟수를 구해봅시다.
3, 5입니다. 뭔가 이제 여기서 규칙이 등장합니다. 피보나치 4는 3입니다. 5는 5입니다.
처음에 피보나치 fibo0, fibi1에 서로 역순 0, 1을 넣어줬습니다.
N이라는 숫자가 들어갔다면 이제 원하는 숫자까지 반복해주면 fibo0은 넣은 값 N의 전 피보나치 수, fibo1을 N의 피보나치입니다.
그리고 나서 출력해주면 됩니다.
