백준 1003 피보나치 함수
오늘은 백준 1003번을 풀어보자.
피보나치수열은 유명하지만 설명하자면
1, 1, 2, 3, 5, 8, 13, 21...
앞에 두 자리를 더한 숫자를 써주면서 계속 쌓아나간다고 보면 된다. 공식으로는 아래와 같다.
F(0) = 1
F(1) = 1
F(n+2) = F(n+1) + F(n)
이런게 있다 정도로만 이해하고 넘어가면 되겠다.
우선 피보나치 함수가 주어져 있다. (fibonacci라는 이름이 기니까 보기 쉽게 f로 줄인다.)
int f(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return f(n‐1) + f(n‐2);
}
}위 함수에 인자로 3을 입력하면 어떻게 되는지 보자.
f(3) = f(3-1) + f(3-2)
= f(2) + f(1)
= ( f(1) + f(0) ) + 1
= ( 1 + 0 ) + 1 // 출력은 101 이 되겠다.
= 2
문제는 0이 몇 번 출력되었는지 1이 몇 번 출력되었는지 각각 출력하라고 한다. 위와 같이 3을 넣어줬다면 101이 출력되며 0이 1번 출력되었고 1이 두 번 출력되었다.
답은 아주 단순하게 구할 수 있다. 전역 변수 zero, one 를 각각 0으로 초기화시켜서 만들어주고 0이 출력되는 조건문에 zero++, 1이 출력되는 조건문에 one++를 해주어 이들을 각각 출력해주면 된다.
아래 문제에 맞게 코딩을 해보자.
#include <iostream>
int zero=0, one=0;
int f(int n) {
if (n == 0) {
zero++;
return 0;
} else if (n == 1) {
one++;
return 1;
} else {
return f(n‐1) + f(n‐2);
}
}
int main(){
int t, number;
std::cin >> t;
while(t--){
zero = 0;// 매 루프마다 초기화하여야함
one = 0;
std::cin >> number;
f(number);
std::cout << zero << " " << one << "\n";
}
return 0;
}위 코드가 잘 실행되는지 먼저 콘솔에서 확인해보자.
첫 줄의 테스트 횟수는 5로 설정하였고
0~4까지 입력해보았다. 각각 출력 값이 잘 나온다. 이대로 코드를 제출하면 아래와 같이 실패하게 될 것이다.
이 문제의 조건은 아래 이미지와 같다.
즉 제출한 코드가 0.25초를 초과하여 실패하게 된 것이다.
이제 우리는 우리가 작성한 코드를 최적화를 진행하여 0.25초 안에 테스트를 통과해야 한다.
위에 제출한 코드가 느린 이유를 먼저 파악해보자.
1. 재귀 함수
우선 재귀 함수를 사용하는 것 자체가 성능에 저하가 생긴다. 반복문을 이용한 코드와 재귀함수를 이용한 코드의 속도를 비교하면 반복문이 훨씬 빠르다고 한다.
재귀함수를 사용하는 이유는 반복문보다 보통 코드도 많이 짧고 가독성이 좋다. 이해하기가 반복문보다 수월하다.
서로 이런 장단점이 있어 그때그때 상황에 맞게 사용해주는 것이 좋다.
속도를 올려야 하므로 재귀 함수를 반복문으로 고쳐주면 속도에서 이득을 볼 수 있다.
2. 재귀함수(or 반복문) 남용
피보나치수열은 몇 번을 테스트하던지 그 값이 정해져 있다. 하지만 위 소스 코드를 보면 테스트 횟수를 입력받고 그 횟수만큼 반복하는데 그 반복되는 횟수만큼 피보나치수열도 새로 생성하고 있다.
즉 테스트 횟수가 10번이면 피보나치수열을 반복문을 돌려 10번 다 따로따로 처음부터 값을 구하고 있는 중인 것이다.
피보나치수열을 구하면 배열에 담아 정보를 저장해놓고 바로바로 사용한다면 위와 같은 의미 없는 시간 손해를 줄일 수 있다.
정리하자면 위 소스 코드의 속도 개선을 위해선 재귀 함수를 반복문으로 바꿀 것, 피보나치수열을 배열로 저장해서 배열을 활용할 것.
배열로 저장하는 방법도 아래와 같이 나뉜다.
첫 번째 방법은 테스트 단계에서 입력받을 수 있는 최대 값만큼의 배열을 구해놓고 시작하는 것이다. 반복문이 최초 한 번만 실행되기 때문에 이 또한 빠르다고 볼 수 있다.
두 번째로 빠른 방법은 테스트 단계에서 입력된 값 이하의 피보나치수열만 배열에 담아서 활용하는 방법이다. 테스트 단계에서 앞전에 입력된 값보다 높은 숫자가 입력되면 추가 탐색하는 방법을 사용한다. 이런 방식이면 값에 따라 속도가 일정하지는 않지만 최소 첫 번째 방법 이상의 속도를 낼 수 있다.
세 번째 방법은 배열에 자기가 구해 놓은 값을 모두 직접 입력해서 해당 값을 이용하는 방법이다. 재귀 함수나 반복문을 사용할 필요 없기 때문에 가장 빠른 방법이다.
나는 문제 풀이하면서 재귀 함수를 반복문으로 바꾸는건... 좀 꼼수라는 생각이 들었다. 재귀함수를 이용할 것이며 배열을 구하는 방식은 위에 설명한 세 번째 방법 역시 꼼수로 느껴지기에 두 번째 방식을 사용하여 제한시간을 통과해 보도록 하겠다.
문제에서 제시한 피보나치 함수를 이용해서 0과 1이 몇 번 출력되는지 표를 작성해보고 0과 1이 출력되는 횟수의 공식을 파악해보자.
| N | f(N) | 0의 출력횟수 | 1의 출력횟수 |
| 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 2 | 1 | 1 | 1 |
| 3 | 2 | 1 | 2 |
| 4 | 3 | 2 | 3 |
| 5 | 5 | 3 | 5 |
이 표를 통해 알 수 있듯이 f(n)과 1의 출력 횟수는 0의 출력 횟수보다 인덱스가 1 높은 수치이다. f함수를 0출력 횟수를 기준으로 시작하게 만들고 f(n)과 1의 출력횟수를 f(n+1)로 사용하게 하면 함수 하나로 모든 값을 구할 수 있다.
N의 범위는 0~40까지이고 1의 출력 횟수는 n+1이니 배열 크기는 42까지가 필요하다. 피보나치수열의 배열을 생성할 때 N+1까지 생성하도록 하여야 한다.
이위 방법들을 사용하여 코드를 작성해 보자.
#include <iostream>
int fa[42];
int f(int n) {
if (n == 0) {
fa[n] = 1;
}
else if (n == 1) {
fa[n-1] = 1;
fa[n] = 0;
}
else {
fa[n] = (fa[n-1]? fa[n - 1]:f(n - 1)) + (fa[n-2]? fa[n - 2]:f(n - 2));
}
return fa[n];
}
int main() {
int t, n;
std::cin >> t;
while (t--) {
std::cin >> n;
if (!fa[n+1])
f(n+1);
std::cout << fa[n] << " " << fa[n+1] << "\n";
}
return 0;
}
위와 같이 나온다. 4ms로 통과하였다.
이 소스코드를 분석해보면 f함수가 재귀 함수를 사용하긴 하는데 삼항연산자로 배열에 값이 이미 있으면 재귀하지 않도록 설정하였다. 이미 계산한적 있는 수열은 더이상 계산하지 않는 것이다.
int main에서도 배열이 있는지 확인하고 없을 경우 재귀함수를 이용해 없는 배열에 채워준다.
테스트 단계에서 40까지 입력을 한다면 먼저 함수로 다 구해놓고 시작하는 것과 속도 차이는 나지 않을 것이다.
테스트 단계에서 랜덤하게 입력하고 40을 보다 작은 수로 입력되고 끝난다면 조금 더 빨리 끝날 수 있다.
자 위 코드에서 반복문을 사용하게 되면 속도가 더 빨라질까??? 한번 테스트해보자.
#include <iostream>
int fa[42];
int main() {
fa[0] = 1;
fa[1] = 0;
int t, n, count = 2;
std::cin >> t;
while (t--) {
std::cin >> n;
if (!fa[n+1]) {
for (count; count <= n+1; count++) {
fa[count] = fa[count - 1] + fa[count - 2];
}
}
std::cout << fa[n] << " " << fa[n+1] << " " << count << "\n";
}
return 0;
}count라는 변수를 반복문 밖에 따로 정의해서 한번 탐색한 내용을 중복 탐색하지 않도록 했다.
결과는 동일하다..... 이 정도 재귀 함수 사용은 반복문이랑 크게 차이가 없는 것인가??
마지막으로 피보나치수열을 직접 입력하여 컴퓨터가 탐색하는 작업을 완전히 빼주고 시작해보자.
#include <iostream>
int main() {
int t, n;
int fa[42] = { 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155 };
std::cin >> t;
while (t--) {
std::cin >> n;
std::cout << fa[n] << " " << fa[n+1] << "\n";
}
return 0;
}
예상과 다르게 결과가 동일하다. 어째서 이런 문제가 발생하는 걸까..?
재귀 함수를 사용하게 작성된 코드에 입출력문을 c의 scanf와 printf로 바꿔보았다.
#include <stdio.h>
int fa[42];
int f(int n) {
if (n == 0) {
fa[n] = 1;
}
else if (n == 1) {
fa[n - 1] = 1;
fa[n] = 0;
}
else {
fa[n] = (fa[n - 1] ? fa[n - 1] : f(n - 1)) + (fa[n - 2] ? fa[n - 2] : f(n - 2));
}
return fa[n];
}
int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
if (!fa[n + 1])
f(n + 1);
printf("%d %d\n", fa[n], fa[n+1]);;
}
return 0;
}
문제는 iostream의 입출력 방식이었다... 해당 내용에 관해서는 다른 글로 찾아오겠다. iostream의 문제를 제외하고 보면 이미 이 코드의 실행 속도는 0ms에 달하는 속도여서 그이 상의 최적화가 의미가 없었던 것으로 보인다.
뭐가 문제였을까 고민을 한참 했는데.. 이런 엉뚱한 결과가 나올지는 몰랐다. 백준 문제를 어떻게 풀었는지 기록을 남길 겸 혹은 누군가에게 작은 도움이라도 될까 싶어서 하나하나 작성 중이지만.. 여러 시행착오를 겪으며 글하나 작성하는데 3시간은 넘게 걸리는 것 같다. 후아.... 계속계속 하다보면 노하우가 생겨 시간이 단축되리라 믿으며 꾸준히 진행해 보겠다.