[다이나믹 프로그래밍] 예제1 - 피보나치 수열

[이코테] 예제1 - 피보나치 수열

(한줄평) 다이나믹 프로그래밍의 대표적인 예제로 어렵지 않게 풀 수 있는 문제

(풀이1) 단순 재귀

풀이 시간: 1분 이내

1) 문제 해결 아이디어

단순 재귀 함수로 구현했을 때 시간복잡도는 O(2**n)이다. 

이미 계산한 것에 대해 호출할 때마다 또 계산을 하기 때문에 n이 커질수록 수행 시간이 기하급수적으로 늘어나는 문제가 있다. 예를 들어, f(6)을 호출할 때 f(3)이 3번이나 호출된다. f(100)이라면 어마어마한 연산을 수행하는데 수백억년이 넘어간다.

 

2) 소스코드

# 1. 피보나치 수열(단순 재귀)
def fibo(x):
  if x == 1 or x == 2:
    return 1
  return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

(풀이2) top-down (하향식)

풀이 시간: 5분 이내

1) 문제 해결 아이디어

메모이제이션 기법을 사용해 탑다운 방식으로 문제를 해결하였다. 탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식으로 재귀를 이용하여 문제를 해결한다. 하지만 한 번 계산한 결과는 리스트(d)에 저장해두고 다시 호출하면 그대로 가져오면 된다. 호출을 할 때 기록된 값이면 바로 그 갑을 리턴하고 아니면 계산 후에 값을 리턴한다.

 

2) 소스코드

# 2. 피보나치 수열(top-down)
d = [0] * 100  # 메모

def fibo(x):
  if x == 1 or x == 2:
    return 1
  # 기록된 값이면 바로 리턴
  if d[x] != 0:  return d[x]
  # 기록된 값이 아니면 계산후 리턴
  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]

 

(풀이3) bottom-up (상향식)

풀이 시간: 5분 이내

1) 문제 해결 아이디어

바텀업 방식은 작은 문제부터 차근차근 답을 도출하는 방식으로 반복문을 이용하여 문제를 해결한다. 탑다운 방식에서 메모이제이션 기법을 사용해 결과를 리스트에 저장해두는 것처럼 결과 저장용 리스트(DP 테이블)에 값을 저장해 놓고 가져오는 방식을 사용한다.

 

2) 소스코드

# 3. 피보나치 수열(bottom-up)
d = [0] * 100  # DP 테이블

d[1], d[2] = 1, 1  # 첫 번째, 두 번째 수는 1로 초기화
n = 99

# n번째 피보나치 수열 값 구하기
for i in range(3, n + 1):
  d[i] = d[i - 1] + d[i - 2]

print(d[n])