다이나믹 프로그래밍
다이나믹 프로그래밍
연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘, 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시킬 수 있는 방법, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법
예시
1. 피보나치 수열
점화식
프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현이 가능하다.
피보나치 함수 코드
# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
이렇게 코드를 작성하면 심각한 문제가 발생할 수 있다.
f(6)에서의 호출 과정
f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다.
시간 복잡도로 표현을 하면 O(2^n)의 지수 시간이 소요된다고 표현한다.
f(3)은 총 3번이 호출되었다.
이렇게 호출 횟수가 많아지면 굉장히 많은 연산을 해야 한다.
이런 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
하지만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이런 조건을 만족하는 대표적인 예이다.
이 문제를 메모이제이션 기법을 사용해서 해결해보자.
메모이제이션: 다이나믹 프로그래밍을 구현하는 방법 중 한 종류, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
피보나치 수열 소스코드(탑 다운)
# 한 번 계산된 결과를 메모이제이션(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))
이렇게 코드를 작성하면 99번째 피보나치를 구하도록 했음에도 금방 정답을 도출하는 것을 알수 있다.
정리하면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
피보나치 수열 소스코드(보텀 업)
# 앞서 계산된 결과를 저장하기 위한 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])