피보나치 수열
-
피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍을 활용해 효과적으로 계산할 수 있습니다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...
-
점화식이란 인접한 항들 사이의 관계식을 의미합니다.
-
피보나치 수열을 점화식으로 표현하면 다음과 같습니다.
a_n = a_n-1 + a_n-2, a_1 = 1, a_2 = 1
-
피보나치 수열이 계산되는 과정은 트리로 표현이 가능합니다.
단순재귀코드
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(5))- 단순재귀로 피보나치를 구현하면 f(2)와 같이 중복된 연산을 여러번 수행합니다. 숫자가 커질수록 기하급수적으로 연산이 늡니다.
- 지수 시간복잡도를 가집니다. O(N^2) ※ f(30)은 약 10억번의 연산을 수행해야합니다. f(100)은 훨씬 더 많아집니다.
다이나믹 프로그래밍의 조건
1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있습니다.
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 수행합니다.
- 트리로 시각화한 것에서 쉽게 볼 수 있듯이, 피보나치 수열은 위 두개 조건을 만족합니다.
다이나믹 프로그래밍의 종류
1. 하향식
2. 상향식
1. 하향식
- 하향식에서 memoization 기법을 사용합니다.
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다. 캐싱이라고도 부릅니다.
- 실제로 보통 다이나믹 프로그래밍에서 사용하는 배열의 변수명을 dp, dp 테이블, d 등으로 설정합니다.
피보나치수열 - 하향식 다이나믹 프로그래밍
# 한 번 계산된 결과를 memoization하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현(하향식 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일때 1 반환)
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]
print(fibo(99))2. 상향식
- 작은 문제를 먼저 해결해서 저장해놓고, 앞으로의 큰 문제들을 풀어갑니다.
피보나치수열 - 상향식 다이나믹 프로그래밍
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수를 반복문으로 구현(상향식 다이나믹 프로그래밍)
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])- 이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리합니다.
- memoization을 이용하는 경우 피보나치 수열 함수의 시간복잡도는 O(N)입니다.
분할정복
- 최적 부분 구조를 가집니다. 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결하는 상황에 해당됩니다.
- 동일한 부분 문제가 반복적으로 계산되지 않습니다. (※ 다이나믹 프로그래밍과 차이점)
분할정복예시 : 퀵정렬
- 퀵정렬은 큰 문제를 작은 문제로 나누어 해결합니다.(최적 부분 구조)
- 동일한 부분 문제가 반복적으로 계산되지 않습니다.
- 예를 들어, 첫 pivot인 5를 기준으로 정렬이 한번 이루어지고나면(분할완료) 더 이상 5의 위치는 변경되지 않습니다.
- 즉, 5를 기준으로 정렬이되고 분할이 이루어지는 과정있었던 연산 중 또 처리되는 것은 없습니다.
- 따라서 이 문제는 다이나믹 프로그래밍이 아닌 분할정복 문제에 해당합니다.
- 퀵정렬 뿐만 아니라, 병합정렬 등과 같은 알고리즘도 분할정복에 해당합니다.
yozzum