[알고리즘] 다이나믹 프로그래밍(동적 계획법)
[다이나믹 프로그래밍]
정의:
다이나믹 프로그래밍(Dynamic Programming)이란, 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
우선, 다이나믹 프로그래밍으로 해결할 수 있는 예시인 피보나치수열 문제를 구하는 과정을 살펴보자.
어떤 수열의 항이 앞의 두 항의 합과 같은 수열을 피보나치 수열이라 하며 그림으로 나타내면 아래와 같다.
- n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
- 첫 번째와 두 번째 피보나치 수 = 1
이러한 피보나치 수열 문제를 일반적으로 프로그래밍 코드로 작성하면 문제가 발생하게 되는데,
f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나게 된다.
빅오 표기법을 사용하여 O(2N)의 지수 시간이 소요된다고 할 때 N=30이면, 약 10억 가량의 연산을 수행해야 한다.
위 그림에서 살펴보면 동일한 함수가 반복적으로 호출된다.
이미 계산한 함수를 다시 불러와서 계산하기 때문에 시간 복잡도가 커지게 된다.
이런 문제를 효율적으로 해결하기 위해 바로 다이나믹 프로그래밍을 사용한다.
다이나믹 프로그래밍
다이나믹 프로그래밍을 항상 사용할 수는 없으며 아래의 두 조건을 충족해야만 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
다이나믹 프로그래밍을 구현하는 방법 중 하나로 메모이제이션(Memoization)이란 기법이 있는데,
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다.
메모제이션 혹은 캐싱(Caching)이라고도 한다.
메모제이션을 구현한 코드를 살펴보자.
# 한 번 계산된 결과를 메모이제이션(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(6))
위의 해법을 그래프로 나타내면 6번째 피보나치 수를 호출할 때 그림처럼 색칠된 노드만을 방문하게 된다.
위의 코드는 재귀 함수를 사용한 것인데,
컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 과정이 필요하기 때문에 오버헤드가 발생할 가능성이 있다.
재귀 함수 대신 반복문을 사용하면 오버헤드 문제를 줄일 수 있다.
오버헤드: 프로그램의 실행흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때 , 추가적으로 시간,메모리,자원이 사용되는 현상
다이나믹 프로그래밍을 구현하는 방식은 아래 두가지이다.
탑다운(Top-Down): 재귀 함수를 사용하여 다이나믹 프로그래밍을 구현하는 방식
보텀업(Bottom-Up): 단순히 반복문을 사용하여 다이나믹 프로그래밍을 구현하는 방식
탑다운 방식은 하향식, 보텀업 방식은 상향식이라고도 한다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이며,
보텀업 방식을 코드로 나타내면 아래와 같다.
# 앞서 계산된 결과를 저장하기 위한 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])
자료출처:
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저
https://gamestory2.tistory.com/15 [베베의 개발일지]