피보나치 수열을 다양한 방법으로 구하기
알고리즘을 공부할 때 기본적인 문제로 등장하는 피보나치 수열. 난이도가 어렵지는 않지만 반복문만을 사용해서 구할 수도 있고, 재귀를 사용해서 구할 수도, 메모리제이션까지 적용하여 풀 수도 있다. 같은 문제를 다양한 방법으로 반복적으로 풀 수 있기 때문에 굉장히 좋은 문제라고 생각한다.
0. 피보나치 수열 점화식
f(0) = 0
f(1) = f(2) = 1
f(n) = f(n-1) + f(n-2)
1. 피보나치 수열 for문으로 구하기
arr = []
def fibo(n):
for i in range(n+1):
if i == 0:
arr.append(0)
elif n == 1 or n == 2:
arr.append(1)
else:
arr.append(arr[n-1] + arr[n-2])
return arr[n]
n번째 피보나치 수열을 구하기 위해 0부터 n까지의 값을 차근차근 계산한다. n이 작은 수 일 때는 상관 없지만 n이 큰 수 일 때 알맞은 방법은 아니다. 처음 구현할 때는 arr에 append 하지 않고 값을 바로 할당 하려고 했었는데, 파이썬에서 값이 없는 배열의 인덱스에 접근하는 것이 불가능해서 append 로 하나씩 값을 더해갔다.
2. 피보나치 수열 재귀로 구하기
def fibo(n):
if n == 0:
return 0
elif 0 < n <= 2:
return 1
else:
return fibo(n-1) + fibo(n-2)
점화식을 통해 확인한 것 처럼 n번 째 피보나치 수열은 f(n) = f(n-1) + f(n-2) 로 구할 수 있다. 결국 함수 fibo를 반복해서 호출함으로써 계산하는 것이기 때문에 재귀로 풀기에 적합하다. 손으로 하나씩 적으면 알 수 있는데, 마지막 줄의 fibo(n-2)는 이미 fibo(n-1)이 계산한 값을 또 다시 계산하는 구조여서 반복문과 마찬가지로 n이 큰 수 일 때 사용하기는 힘들다.
3. 피보나치 수열 재귀 + 메모리제이션으로 구하기
memo = {0:0, 1:1, 2:1}
def fibo(n):
if n <= 2:
return 1
if n not in memo:
memo[n] = fibo(n-1) + fibo(n-2)
return memo[n]
앞서 살펴본 재귀의 방법에서 이미 계산한 값을 다시 계산하지 않도록 개선한 방법이다.
재귀에 익숙하지 않은 사람은 마지막 줄의 return memo[n]이 함수 fibo를 호출할 때 마다 항상 실행될 것 같지만, memo[n]을 구할 때까지 재귀 함수가 계속 호출되어 스택에 쌓이고 있기 때문에 다음 줄로 넘어가지 않는다. 최종적으로 memo[n]이 구해지면 return문을 만나 함수가 종료된다.