코딩테스트 (2) - 피보나치 수열
서론
오늘 풀어볼 문제는 백준에서 제공하는 코딩테스트이다.
피보나치 수열과 관련된 문제로 수학을 잘한다면 쉽게 풀 수 있을 것이다.
문제 설명
다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
c1int fibonacci(int n) { 2 if (n == 0) { 3 printf("0"); 4 return 0; 5 } else if (n == 1) { 6 printf("1"); 7 return 1; 8 } else { 9 return fibonacci(n‐1) + fibonacci(n‐2); 10 } 11}
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
fibonacci(0)은 0을 출력하고, 0을 리턴한다.
fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.
1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
출력
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
피보나치 수열?
문제를 이해하려면 피보나치 수열이 무엇인지를 우선 알아야한다.
피보나치 수열이란 이탈리아의 수학자 피보나치가 제시한 문제이다.
갓 태어난 토끼 암수 한 쌍이 있다.
이 토끼들이 태어난 지 두달이 되면 한쌍의 토끼를 낳는다.
새로 태어난 토끼 한 쌍도 태어난 지 두달이 되는 달부터 한쌍의 토끼를 낳는다.
일년 후 토끼는 모두 몇 쌍이 될까?
(단, 토끼는 중간에 죽지 않는다.)
즉 처음 토끼가 새끼를 낳는데 걸리는 시간은 총 한달, 그럼 첫쨋달의 토끼는 한쌍.
둘째달에도 토끼가 한쌍이고, 이제 새끼를 낳을 수 있으니 셋째달에는 두쌍.
넷째달에는 처음 토끼가 한쌍의 토끼를 다시 낳으니 세쌍.
다섯째달에는 처음 토끼가 한쌍의 토끼를 다시 낳고 둘째달 태어난 토끼가 새끼를 낳으니 두쌍이 더해져서 총 다섯쌍...
이런 식으로 토끼의 수가 늘어난다.
여기서 중요하게 봐야할 법칙은 n+2번째 달에 태어난 토끼이다.
n번째 달에 태어난 토끼는 n+2번째 달에 새끼를 낳을 수 있지만 n+1번째 달에 태어난 토끼는 새키를 낳을 수 없다.
그렇기때문에 n+2번째 달의 토끼의 수는 n번째 달의 토끼수 + n+1번째 달의 토끼수가 되는 것이다.
위 문제를 수열로 나타내면
1, 1, 2, 3, 5, 8, 13, ...
이런 형태를 가지게 되는데 이게 피보나치 수열이다.
쉽게 설명하자면 앞의 두 항을 더한 값이 다음 항이 되는 수열이다.
첫째항 1과 둘째항 1을 더한값 2가 셋째항이 되고,
넷째항은 둘째항 1과 셋째항 2을 더한값인 3이 되는 식이다.
뭐 더 자세하게 이해를 하면 좋겠지만 오늘 문제를 푸는데는 이정도만 이해하면 된다.
그럼 이제 문제를 풀어보자.
풀이
위의 문제에서 피보나치 수열에 관한 함수를 제공해줬다.
그럼 이런 의문이 들 것이다.
'그냥 저 함수를 이용해서 답을 구하면 안되나요?'
물론 가능은 하다.
다만 프로그램이 수열을 돌리는데 걸리는 시간이 엄청 들기때문에 문제를 풀어보면 기준이 되는 시간을 초과하게 되어 오답이 되어버린다.
그렇다면 어떻게 해야 할까?
우선 위의 함수를 이해해보자.
n번째 피보나치 수열 항을 구한다고 치자.(이때 n은 1 보다 큼)
그렇다면 재귀 함수가 발생할 것이다.
n이 5라고 한다면 fibonacci(4), fibonacci(3) 이렇게 실행된다.
다시 4라는 값을 받은 재귀함수에서는 3과 2를 매개변수로 재귀함수를 실행한다.
3 이라는 값을 받은 재귀함수에서는 2와 1를 매개변수로 재귀함수를 실행한다.
이렇게 끝까지 내려가면 0과 1 둘중에 하나의 값이 되고, 그 값이 리턴되고 리턴되어 더해지고 마지막에 리턴되는 값이 바로 n번째 피보나치 수열의 항이다.
하지만 우리가 구해야하는 값은 피보나치 수열 전체가 아닌 위의 함수를 돌렸을 때 0과 1이 나오는 횟수를 알아내야한다.
일일이 저 함수를 돌리며 찾는게 아니라면 어떻게 해야할까?
n번째 피보나치 수열의 항의 값은 함수를 돌려서 나온 모든 0과 1을 더한 값이다.
그렇다면 fibonacci(2)의 값은 fibonacci(1) 과 fibonacci(0) 을 더한 값이다.
그리고 fibonacci(3)은 fibonacci(2) 와 fibonacci(1),
즉 fibonacci(1) + fibonacci(1) + fibonacci(0)을 더한 값이다.
이런식으로 계산해보면 즉 n번째 피보나치 함수의 값은
1fibonacci(n) + 0fibonacci(n-1) 이 된다.
이를 이용해 직접 피보나치 수열을 돌리는 것이 아닌 n번째 피보나치와 n-1번째 피보나치 수열의 값만 알 수 있다면 시간초과가 되지 않고 문제를 풀 수 있다.
우선 아래 내가 푼 풀이를 보자.
c1#include <iostream> 2 3void fibonacci(int n); 4 5int main() { 6 int t,n; 7 std::cin >> t; 8 9 for (int i = 0; i < t; i++) { 10 std::cin >> n; 11 fibonacci(n); 12 } 13 14 return 0; 15} 16 17void fibonacci(int n) { 18 int a = 0; 19 int b = 1; 20 int c = 0; 21 22 for (int i = 1; i <= n; i++) { 23 a = b; 24 b = c; 25 c = a + b; 26 } 27 28 std::cout << b << ' ' << c << std::endl; 29}
- 시행횟수 t를 입력받고 그 만큼 반복문을 돌린다.
- 반복문내에서 n을 입력받고 fibonacci(n) 을 실행시킨다.
- a와 c는 피보나치 수열의 0번째 항 b는 fibonacci 수열의 1번째항을 준비한다.
- n만큼 반복문을 돌린다.
- a는 0번째 항에서 다음항인 b의 값이 된다.
- b는 c의 값이 되고 c는 0번째 항과 첫번째 항을 합친 두번째 항의 값을 가진다.
- 그리고 다시 a는 N-2의 항이 되고 b는 N-1의 항, 그리고 c는 두 값을 더한 N의 항이 된다.
- 위의 과정을 n번 반복하면 n-1번째 항인 b, 그리고 n번째 항인 c가 되고 이의 값은 각각 0과 1이 나온 횟수와 같다.
마치며
오늘 문제는 수학적으로 접근해야해서 조금 복잡한 문제가 된 것 같다.
백준에서 주는 문제들은 뭔가 하나씩 함정이 있는 느낌이라 조금 더 깊게 생각해야한다는 생각이 든다.
오늘 문제도 처음에 준 함수에 시선을 뺏겨버리면 시간 초과로 오류가 나게 될 것이니 가끔은 사고의 방향을 바꿔보는 것도 괜찮은 것 같다.