n번째 피보나치 수 출력하기(재귀)(메모이제이션)(설명) [1899 / 076B] Time Limit(Test case) : (ms) Number of users who solved : 0 Total Tried : 0 The Champion of this Problem (C++) : N/A My Best Submission (C++) : N/A [koistudy.net (T. HS Jeon 2017)] Background *주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다. ------ n번째 피보나치 수를 1000000007(10억7)로 나눈 나머지를 출력하시오. (단, 반복문은 사용할 수 없다.) 참고 다중 재귀는 하나의 함수가 자기 자신과 같은 형태의 보다 작은 함수를 여러 개 호출하게 되므로, 중복 호출이 발생하게 된다. 예를 들어 피보나치 수를 계산하는 다음과 같은 점화 관계식을 만들고, f(5)의 값을 얻어내기 위해서는, f(5) = f(4) + f(3) = (f(3)+f(2)) + f(3) <-- f(3) 중복 호출발생 = ((f(2)+f(1)) + f(2)) + f(3) = ((f(2)+f(1)) + f(2)) + (f(2)+f(1)) 과 같이 재귀 함수가 여러 번 중복 호출 된다. f(99)를 계산하기 위해서는 얼마나 많은 중복 호출이 이루어질까? 이런 형태로 다중 재귀에 의해 재귀함수가 호출되는 깊이가 증가하게 되면, 이전에 호출했던 똑같은 재귀 함수의 중복 호출이 기하급수적으로 증가하게 되어, 재귀호출 상태를 저장해 두는 공간이 부족해 프로그램 실행 중 오류로 중단되거나, 제한 시간 내에 원하는 결과를 얻어낼 수 없게 된다. 재귀 함수 설계는 주어진 문제 상황을 자기 유사적인 보다 작은 문제로 나누어 해결할 수 있는 경우, 보다 작은 문제 상황과의 관계만을 이용해 매우 간단히 설계할 수 있다는 장점이 있지만, 위와 같은 중복 호출 상황이 매우 많이 발생할 수 있기 때문에 비효율적이라고 생각할 수도 있다. 하지만, 매우 간단한 아이디어 한 가지를 적용하면 재귀 함수를 이용해 복잡한 문제 상황을 간단히 관계식으로 쪼개어 표현하고, 중복 호출되는 횟수를 최소한으로 만들어 매우 효과적인 문제해결 프로그래밍 코드를 작성할 수 있다. 그렇게 만드는 가장 핵심적인 아이디어는? - “계산한 적이 없는 것은 그 값을 계산한 후 그 기록해 둔다.” - “계산한 적이 있다면, 기록해 두었던 값을 바로 사용하고 다시 계산할 필요가 없다.” 로 설명할 수 있다. 일반적인 다중 재귀 함수로 n번째 피보나치 수를 계산하는 문제에 대해서 하향식 재귀 설계 방법을 적용하면, 다음과 같이 설계가 되지만, k값이 커지면 중복 호출이 아주 많이 발생하게 된다. long long f(int k) { if(k <= 2) return 1; return f(k-2)+f(k-1); } 이 상태에서 어떤 f(k)를 계산 할 때, 계산 여부를 기록해 두기 위한 체크 배열을 추가하고, int chk[100]; //f(k)가 호출되면, 호출 했다는 것을 1로 기록해 두기 위한 배열 long long f(int k) { if(k <= 2) return 1; return f(k-2)+f(k-1); } 계산한 결과 값을 기록해 두기 위한 결과 값 배열을 추가하고, int chk[100]; //f(k)가 호출되면, 호출 했다는 것을 1로 기록해 두기 위한 배열 long long d[100]; //f(k)의 값을 기록해 두기 위한 배열 long long f(int k) { if(k <= 2) return 1; return f(k-2)+f(k-1); } 기록해 둔 결과를 바로 사용하는 아이디어를 적용하면, int chk[100]; //f(k)의 호출 여부를 기록/확인하기 위한 배열 long long d[100]; //f(k)의 값을 기록해 두기 위한 배열 long long f(int k) { if(chk[k] == 1) return d[k]; //계산한 적이 있었다면, 그 결과 값을 리턴한다. chk[k]=1; //계산한 적이 없었으니, 계산했다고 체크한다. if(k <= 2) return d[k]=1; //d[k]에 값을 저장하고, 저장된 값을 리턴한다. return d[k]=f(k-2)+f(k-1); //계산한 결과 값을 d[k]에 저장하고, 저장된 값을 리턴한다. } 와 같이 바꿀 수 있다. 이러한 방법을 메모이제이션(memoization)이라고 한다. 위와 같은 아이디어를 이용해 f(n)을 호출하여 n 번째 피보나치 수를 매우 빠르게 계산해 출력하는 메모이제이션 예시코드는 다음과 같이 작성할 수 있다. #include int n; int chk[110]; //f(k)가 호출되면, 호출 했다는 것을 1로 기록해 두기 위한 배열 long long d[110]; //f(k)의 값을 기록해 두기 위한 배열 long long f(int k) { if(chk[k] == 1) return d[k]; chk[k]=1; if(k <= 2) return d[k]=1; return d[k]=f(k-2)+f(k-1); } int main() { scanf("%d", &n); printf("%lld\n", f(n)); } Input int 형 정수(n) 1개가 입력된다. (1 <= n <= 100) Output n 번째 피보나치 수를 출력한다. (단, 수가 매우 크기 때문에 1000000007(10억7)로 나눈 값을 출력하도록 한다.) IO Example 입력 6 출력 8