연산속도와 메모리 공간을 최대한 효율적으로 활용할수 있는 알고리즘을 작성해야 하며, 이를 통해 연산속도를 비약적으로 증가시킬 수 있는 방법이 다이나믹 프로그래밍(Dynamic Programming) or 동적계획법이다.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시는 피보나치 수열이다.
점화식이란 인접한 항들 사이의 관계식을 의미하며, 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다.
- 인접한 3개의 항에 대해서 식이 정의되는 인접 3항간 점화식
수학적 점화식을 재귀함수를 사용하여 프로그래밍으로 구현할 수 있다.
# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))하지만, 위 코드의 문제점은 n이 커질수록 그 수행시간이 기하급수적으로 늘어난다는 점이다. 시간복잡도 : O(n^2)
하지만, 위 재귀함수를 생각해보면 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 이처럼 피보나치 수열의 점화식을 재귀함수를 사용해 만들수는 있지만, 단순히 매번 계산되도록하면 문제를 효율적으로 해결할 수 없다. 따라서 이러한 문제는 DP를 사용해 효과적으로 해결할 수 있다.
다이나믹 프로그래밍은 다음과 같은 조건을 만족할 때 사용할 수 있다.
1) 큰 문제를 작은 문제로 나눌 수 있다.
2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
이러한 문제를 메모제이션 기법을 사용해서 해결해보자. 메모제이션(Memozation) 기법이란, 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
이를 구현하는 방법은 한번 구한 정보를 리스트에 저장하여, 다이나믹 프로그래밍을 재귀적으로 수행하다가 가은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오는 것이다. 소스코드는 다음과 같다.
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
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))다시 한번 정리해보자면, 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
다이나믹 프로그래밍과 분할 정복의 차이점
분할 정복의 대표적인 에시인 퀵 정렬의 경우 한번 기준 원소(Pivot)이 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 반면에 다이나믹 프로그래밍은 한번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대해 답을 저장해 놓고, 이를 반환하여 효율적으로 문제를 해결할 수 있다.
다이나믹 프로그래밍을 사용한 피보나치 수열 알고리즘의 시간 복잡도
: 각각의 n에 대해 한번씩만 계산하면 되기 때문에 O(n)
이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을
큰 문제를 해결하기 위하여 작은 문제를 호출하는 '탑다운 방식'이라고 한다.
이에 반해 다음과 같이 단순히 반복문을 이용한 소스코드는 작은 문제부터 차근차근 답을 도출해 나가는 보텀업 방식도 존재한다.
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])탑다운(메모제이션) 방식 -> 하향식
바텀업 방식 -> 상향식
이라고 하며,
다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다.
바텀업 방식에서 사용되는 결과 저장용 리스트는 DP테이블이라고 부르며, 메모제이션은 탑다운 방식에 국한되어 사용되는 표현
수열은 배열, 리스트로 구현될 뿐만 아니라 dict와 같은 다른 자료형을 이용할 수도 있다.
다이나믹 프로그래밍 문제에 접근하는 첫번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복여부를 확인해보면 된다.
