-
문제 f(0) = 1, f(1) = 1을 반환합니다. 먼저 ( x , y ) 를 x = 0의 출현, y = 1의 출현을 맵핑한 notation으로 쓰겠습니다.
예시에서 f(3) = f(2) + f(1) = { f(1) + f(0) } + f(1) = 1 + 0 + 1 -> (1, 2)
그렇다면
f(4) = f(3) + f(2) = { f(2) + f (1) } + { f(1) + f(0) }= [ { f(1) + f(0) } + f(1) ] + { f(1) + f(0) } = 1 + 0 + 1 + 1 + 0 -> ( 2, 3 )
직감적으로 피보나치 수를 계산하라는 느낌이 옵니다. 그러나 그림을 통해 조금 더 확신을 갖고 어떤 점에서 동적 계획법을 활용하면 좋은지 확인해보는 것도 좋습니다.
f(2)의 결과값이 f(3)의 결과값을 구하는데 쓰이고 있습니다. 말로 풀어 쓰면 f(3)은 f(2)의 0과 1의 개수를 요구합니다. 즉 f(3) = (1,1) + (0, 1) = (1, 2)가 됩니다. 그럼 f(4) = f(3) + f(2) = (1,2) + (1,1) = (2, 3)이 되겠습니다. 이제 완전히 피보나치 수가 나타났습니다. 이 문제는 단순히 피보나치 수를 두 개 구하면 됩니다.
같은 결과값을 계속 사용하기 때문에 주어진 수 만큼 계산을 하되, 어떤 공간에 중간계산 결과값을 저장하고 필요할 때 마다 꺼내 쓰면 참 좋겠습니다. 어려운 말로 Memoization이라고 합니다.
난잡합니다 그런데 생각해보면 피보나치 수는 행렬을 이용해서 구할 수도 있었습니다. 심지어 행렬의 경우, 현재 수와 이전 수까지 함께 볼 수 있다는 엄청난 장점이 있었습니다. 그럼 간단하게 행렬과 벡터 연산을 정의하여 주어진 만큼 반복하기만 한다면 훨씬 쉽게 풀 수 있을 것입니다. 세세하게 정의할 필요가 없으니 행렬과 벡터의 곱에서 2x2행렬은 Class를 만들어주고 2x1벡터는 수의 pair로 표현하기로 합니다. Matrix로 정의해야 하는데 깜빡하고 Vector라고 썼습니다.
