injoon2018   2년 전

풀다가 도저히 안풀려서 질문게시판의 다른 분들 질문과 코드를 봤는데

대부분 규칙을 발견하셔서 풀으셨더라고요. 0과 1이 몇 번 호출되는지 그 조차도 피보나치 수열이더라고요.

그 방법이 더 좋지만, 구현을 하다보니 구현에 대한 욕심이 있는데

메모이제이션을 쓰면, 이미 구한 답은 함수를 들어가지 않으니, 전역변수로 0과 1의 함수를 들어갈때마다 ++ 하는 방식으로 구현은 불가능한가요?

ckdgus2482   2년 전

규칙을 발견해서 풀었다라고 보셨는데 그렇게 보실 수도 있지만 0과 1이 호출되는 횟수가 피보나치 수열을 이루는것은 수열 특성상 자연스럽게 그렇게 되는 것입니다

fibo(n)은 fibo(n)이 fibo(1)을 호출한 횟수와 같고 fibo(n - 1)은 fibo(n)이 fibo(0)을 호출한 횟수와 같은데

fibo(n - 1)에서 0을 호출한 횟수 + fibo(n - 2)에서 0을 호출한 횟수 = fibo(n)에서 0을 호출한 횟수이며

fibo(n - 1)에서 1을 호출한 횟수 + fibo(n - 2)에서 1을 호출한 횟수 = fibo(n)에서 1을 호출한 횟수입니다

호출 횟수를 나타내는 수열의 점화식이 피보나치와 같으니 당연히 피보나치 수열과 동일해지는 것입니다

fibo(1)에서 1호출횟수는 fibo(1)과 같고 0호출횟수는 fibo(0)과 같으므로 이를 초항으로 잡으면 됩니다

그리고 전역변수로 각각 카운팅하는 방법은 메모이제이션을 하지 않았을때 유효한 방법 아닐까요?

injoon2018   2년 전

' fibo(n)은 fibo(n)이 fibo(1)을 호출한 횟수와 같고 fibo(n - 1)은 fibo(n)이 fibo(0)을 호출한 횟수와 같은데' 이 부분이 바로 이해가가지 않네요

혹시 왜 그런지 이유가 있을까요??

네 그리고 전역변수 카운팅은 메모이제이션을 하니 안되더라고요. 

ckdgus2482   2년 전

네 그부분이 증명하고자 하는 명제입니다

편의상 fibo(n)이 0을 호출한 횟수를 A(fibo(n))으로 정의하고 fibo(n)이 1을 호출한 횟수를 B(fibo(n))으로 정의하겠습니다

그러면 명제는 다음과 같이 표현할 수 있습니다

임의의 자연수 n에 대하여, A(fibo(n)) = fibo(n-1)이고 B(fibo(n)) = fibo(n)이다

이 명제는 수학적 귀납법으로 증명할 수 있습니다

n이 1인 경우

A(fibo(1))은 0인데 fibo(0)도 0이므로 A(fibo(1)) = fibo(0)을 만족하며, B(fibo(1))은 1인데 fibo(1)도 1이므로 B(fibo(1)) = fibo(1)를 만족합니다

n이 2인 경우

A(fibo(2))은 1인데 fibo(1)도 1이므로 A(fibo(2)) = fibo(1)을 만족하며, B(fibo(2))은 1인데 fibo(2)도 1이므로 B(fibo(2)) = fibo(2)를 만족합니다

임의의 n에 대해서  n - 1과 n - 2가 명제를 만족하는 경우

우선 A(fibo(n)) = A(fibo(n - 1)) + A(fibo(n - 2))이고

B(fibo(n)) = B(fibo(n - 1)) + B(fibo(n - 2))인 것은 자명합니다

그리고 n - 1과 n - 2가 명제를 만족한다고 했으므로

A(fibo(n - 1)) = fibo(n - 2)이고 A(fibo(n - 2))는 fibo(n - 3)이므로 A(fibo(n)) = fibo(n - 2) + fibo(n - 3) = fibo(n - 1)입니다

마찬가지로

B(fibo(n - 1)) = fibo(n - 1)이고 B(fibo(n - 2))는 fibo(n - 2)이므로 B(fibo(n)) = fibo(n - 1) + fibo(n - 2) = fibo(n)입니다

따라서 모든 자연수 n에 대해서 해당 명제를 만족한다는 것을 알 수 있습니다


injoon2018   2년 전

감사합니다~ 여러번 읽다보니 이해가 됐습니다!!

ksh4820   2년 전

정말 감사합니다 ~

댓글을 작성하려면 로그인해야 합니다.