1. 문제 조건 확인
피보나치 수에 대한 문제이다. 단, 피보나치 수를 구하는 문제는 아니다. 피보나치 수는 유명한 수열로, 앞의 두항을 더해 다음항을 구하는 구조이다. 조금 써보자면, 0 1 1 2 3 5 8 13 21 34 55... 로 진행된다.
F(n) = F(n-1) + F(n-2) (단 n=0 일때 0, 1일 때 1)
이를 프로그래밍 한다면, 간단히 재귀함수를 이용해 나타낼 수 있다. 그 예가 바로 문제에서 볼수 있다.
이를 이용하면 피보나치 수를 구할 수 있다. 다만, 문제에서 요구하는 것은 위의 재귀 함수를 이용했을 때, fibonacci(0)와 fibonacci(1)의 호출수를 구하는 것이다. 그 예가 문제에 잘 나타나있는데 fibonacci(2)는 fibonacci(1) 과 fibonacci(0)을 호출할 것이므로, 답은 1 1이 될 것이다. fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 호출하고, 다시 fibonacci(2)는 앞선 결과처럼 0과 1을 각각 1번씩 호출하므로 답은 1 2가 된다.
- 입력 조건
T의 테스트 케이스 수를 입력받고, T번 동안 N번째 Fibonnaci 수를 계산한다.
N은 0이상 40미만의 정수
- 출력 조건
각 테스트케이스에 대해서 fibonacci(0)과 fibonacci(1)의 호출 수를 출력한다. fibonacci(0)의 호출 수를 출력하고, fibonacci(1)의 호출 수를 출력하며, 스페이스바로 둘을 구분한다.
2. 문제 풀이
- 아이디어
문제의 시간제한을 보면 0.25초로 굉장히 짧은 시간이다. 시간 제한으로 유추해봤을 때 이 문제를 재귀로 푸는 경우에는 시간제한이 발생할 가능성이 높다. 피보나치 재귀함수의 구조를 살펴보면, n번째 피보나치 수를 구할 때 n-1, n-2번째 피보나치 수를 구하게 될 것이고, 다시 n-1번째 피보나치 수는 n-2, n-3 피보나치 수를 구하게 된다. 이처럼 자세히 보면, n-2번째 피보나치 수가 중복되어 호출되게 된다. 즉 같은 과정을 2번 이상 재귀적으로 호출하게 될 것이기 때문에 시간적 효율성이 떨어진다. 이를 처리해주기 위해서 DP와 Memoization을 이용하고자 했다. 재귀적으로 호출하면서, 이미 호출한 피보나치 수의 경우 더이상 작은 수로 나누어 구하지 않고, 이미 구했던 수를 이용한다.
- 코딩
Memoization과 Dynamic Programming을 이용하기 위해서, fibodp 배열을 전역으로 선언하였다. 또한 fibodp를 2차원배열로 선언하였는데. 첫 숫자는 n번째 피보나치 수를 의미하며, 두번째 숫자는 fibonacci(0) 혹은 fibonacci(1)을 의미한다. 예를 들어 fibodp[3][0]은 3번째 피보나치 수의 fibonacci(0) 호출 수이다.
DP와 Memoization을 위한 배열을 선언한 뒤, fibocheck라는 함수를 작성해 재귀적으로 값을 구할 수 있도록 하였다. 다만, 주어진 fibonacci()함수처럼 피보나치 수를 구할 이유는 없으므로, fibodp의 fibodp[n-1][0], fibodp[n-1][1], fibodp[n-2][0], fibodp[n-2][1]을 확인하고 이미 있는 경우 그 값을 이용 그렇지 않은 경우에는 fibocheck를 호출하여 값을 갱신해 fibodp에 저장할 수 있도록 하였다. 이 작업을 위해서 , fibodp의 [0]과 [1]번째 수는 미리 초기화를 해둔다.
- 분류 : Dynamic Programming, Memoization
반응형
'프로그래밍 > 알고리즘 문제 풀이' 카테고리의 다른 글
| 2942 - 퍼거슨과 사과 (0) | 2018.05.25 |
|---|---|
| 1309 - 동물원 (0) | 2018.05.25 |