hechargu   2년 전

피보나치 점화식 f(n) = f(n-1) + f(n-2) 만을 이용하여 푸는 방법에 대해서 설명합니다.

f(n)      = 1*f(n-1) + 1*f(n-2) = f(n-2) + f(n-3) + f(n-2)

            = 2*f(n-2) + 1*f(n-3) = 2*(f(n-3) + f(n-4)) + f(n-3)

            = 3*f(n-3) + 2*f(n-4) = 3*(f(n-4) + f(n-5)) + 2*f(n-4)

            = 5*f(n-4) + 3*f(n-5) = 5*(f(n-5)+f(n-6)) + 3*f(n-5)

            = 8*f(n-5) + 5*f(n-6) 

            ...

피보나치 점화식을 재귀적으로 풀어서 정리해보면 위와 같은 형태의 식이 나오는데, 자세히 관찰해보면 풀어서 정리할 때마다 피보나치 수 앞에 붙는 계수도 피보나치 수의 형태를 가지고 있음을 확인할 수 있습니다. 이를 이용하여 n에 대한 피보나치 점화식을 n/2에 대한 피보나치 수로 다시 작성해보면 다음과 같습니다.

f(n)       = f(n/2+1) * f(n/2) + f(n/2) * f(n/2-1)

            = (f(n/2) + f(n/2-1)) * f(n/2) + f(n/2) * f(n/2-1)

            = f(n/2)^2 + 2 * f(n/2) * f(n/2-1)

즉, f(n)을 f(n/2)와 f(n/2-1)로 구할 수 있으니 분할정복을 이용하여 빠르게 피보나치 수를 구할수 있게 되었습니다. (분할정복을 이용한 거듭제곱 알고리즘과 형태가 매우 유사합니다.) 

이때 주의해야할 점은 분할정복 도중 n/2를 계산할 때 n이 홀수인 경우인데, 이는 피보나치 점화식을 변형하여 아래와 같이 계산하면 항상 짝수 n에 대하여 n/2이 수행됩니다.

f(n) = f(n-1) + f(n-2) = f(n-1) + f(n-1) - f(n-3) = 2 * f(n-1) - f(n-3)  (n이 홀수일 때, n-1와 n-3은 짝수가 된다.)

또한 위와 같은 방식으로 분할정복을 수행하면 도중에 중복되는 부분문제가 발생하므로, 메모이제이션을 활용해야합니다. (실제로 메모이제이션을 사용하지 않으면 시간초과가 납니다.)

첨부한 소스코드는 위 알고리즘을 구현한 것이고, java 기준 124ms으로 깔끔하게 AC 되었습니다. 비록 행렬 거듭제곱을 이용한 방법에 비해서는 덜 효율적이지만, 순수하게 피보나치 점화식으로 분할정복을 유도할 수 있다는 점에서 꽤나 멋진 접근인 것 같습니다.

jeonsonghyun   2년 전

처음 봤을 때 피보나치 점화식 가지고 뭔가 해보려다 나오는게 없어서 풀이를 찾아봤었는데 이렇게 하는 거였군요

jwpyo0803   1년 전

혹시 고안하신 풀이방법이 선형대수를 사용해 푸는 방식과 근본적으로 연결이 되어있을까요?

hechargu   1년 전

직접적인 연관은 잘 모르겠습니다만, 아마 실제 계산과정에서 분할되는 부분문제는 두 방식이 서로 비슷할 것입니다. 즉 두 방식 사이에 수학적인 연관성이 있다기보단, n/2으로 분할정복한다는 동일한 알고리즘을 서로 다른 접근 방식으로 구현한 것이라고 보면 될듯 합니다.


제가 고안한 방식은 피보나치 수열에만 한정되는 애드혹이며 이와 유사한 접근을 문제마다 찾기도 쉽지않기에, 실제 문제를 풀때는 행렬 거듭제곱을 이용한 일반적인 방식으로 빠르게 구현하는 것이 더욱 효과적일 것입니다.

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