on
다이나믹 프로그래밍 [ 파이썬 ]
다이나믹 프로그래밍 [ 파이썬 ]
중복되는 연산 줄이기
최적의 해를 구하기 위해 시간이 매우 많이 필요하거나, 메모리 공간이 매우 많이 필요한 문제는 컴퓨터로 해결하기 어렵다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문이다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.
다만, 어떤 문제는 메모리 공간을 약간만 더 사용해도 연산속도를 비약적으로 증가 시킬 수 있는 방법이 있다.
바로 다이나믹 프로그래밍(Dynamic Programming) 이다.
먼저 기본 알고리즘으로는 해결하기 어렵지만 다이나믹 프로그래밍으로 해결할 수 있는 문제를 알아보자.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.
피보나치 수열 : 1 1 2 3 5 8 13 21 34 55 89
피보나치 수열은 점화식으로 표현되며 점화식을 보기쉽게 해석하면 아래와 같다.
- n번째 피보나치수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
- 단, 첫번째 피보나치수=1 / 2번째 피보나치 수는 2 이다.
프로그래밍 에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다. 파이썬에서는 리스트 자료형, C/C++이나 자바에서는 배열을 이용해 이를 처리한다. 리스트나 배열 모두 '연속된 많은 데이터'를 처리한다는 점은 동일하다.
그럼 이 피보나치 수를 구하는 과정을 표현해보자 N번째 피보나치 수를 f(n)이라고 할 시 4번째 피보나치 수를 구하려면
함수 f( )를 계속 반복 호출해야한다. 호출 하면서 f(2), f(1)의 차례가되면 항상 값이 1이므로 정지를 하게 될것이다.
위의 원리로 재귀함수를 통해 피보나치수열을 구현한 소스코드는 아래와 같다.
# 피보나치를 재귀함수로 구현
def fibo ( x ):
if x == 1 or x == 2 :
return 1
return fibo ( x - 1 )+ fibo ( x - 2 )
그런데 피보나치 수열의 소스코드를 위 방식대로 구현하는 것에는 심각한 문제가 있다. 바로 f(n)에서 n이 커질수록 수행 시간이 기하 급수적으로 늘어나기 때문이다. 대략 n이 30이면 약 10억번의 연산을 수행해야한다.
예를들어 f(6)을 호출하려고하면 f(1)은 3번 f(2)는4번 f(3)은 3번이 호출 된다. 이렇게 f(n)에서 n이 커질수록 반복 호출해야하는 횟수가 많아진다. f(100)은 약 10의 30승번의 연산을 거쳐야 한다. 이처럼 피보나치 수열의 점화식을 재귀함수로 만들 수는 있지만 단순히 매번 모든 항들을 계산해야 하므로 효율적이지 않다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 하지만 다이나믹 프로그래밍은 항상 사용할 수 잇는게 아닌, 아래의 조건을 만족해야 사용할 수 있다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이 조건을 만족하는 대표 문제이다. 이 문제를 메모이제이션(Memoization)기법을 사용하여 해결해보자, 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모하고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 이걸 캐싱(Caching)이라고도 한다.
메모이제이션을 파이썬으로 구현하려면 한번 구한정보를 리스트에 저장하면 된다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 이전에 썼던 정보가 필요할 때는 이미 구한 정답을 리스트에서 가져오면된다.
피보나치 수열 소스코드(다이나믹 프로그래밍으로 구현)
# 한번 계산된 결과를 기록하기 위한 리스트를만들고 0으로 초기화 한다.
dp =[ 0 ]* 100
# 피보나치 함수 재귀적으로 구현(탑 다운 방식)
def fibo ( x ):
# 종료 조건(1or2 일때 1을 반환)
if x == 1 or x == 2 :
return 1
# 이미 계산한적 있는 문제라면 그대로 반환
if dp [ x ]:
return dp [ x ]
# 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
dp [ x ]= fibo ( x - 1 )+ fibo ( x - 2 )
return dp [ x ]
print ( fibo ( 99 ))
실제 시행해보면 99번째 피보나치 수임에도 금방 정답이 도출 된다. 정리하자면 다이나믹 프로그래밍 이란 큰 문제를 작게 나눈 후, 같은 문제라면 한번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
위 방법은 퀵 정렬과도 비슷한데, 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할정복(Divide and Conquer) 알고리즘으로 분류된다. 다이나믹 프로그래밍과의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
퀵정렬은 한 번 기준 원소(Pivot)이 자리를 변경해서 자리를 잡게 되면 그 기준 원소 위치는 더 이상 바뀌지 않고 그 피벗 값을 다시 처리하는 부분 문제는 존재하지 않지만 다이나믹 프로그래밍은 한번 해결했던 문제를 다시금 해결한다는 점이 특징이다. (이미 해결한 문제를 저장해놧다 반환)
다이나믹 프로그래밍으로 피보나치 수열 알고리즘을 풀었을 때 시간복잡도는 O(N) 이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)에 사용, f(2)는 f(3)에 사용 되는 방식으로 이어지기 때문이다.
이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑 다운(Top-Down) 방식 이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식(Botton-up)이라고 말한다. 아래는 보텀업 방식으로 구현한 피보나치 수열의 소스코드이다.
보텀업 방식으로 구현한 피보나치 수열의 소스코드
# 한번 계산된 결과를 기록하기 위한 리스트를만들고 0으로 초기화 한다.
dp =[ 0 ]* 100
# 첫 번째, 두 번째는 1
dp [ 1 ]= 1
dp [ 2 ]= 2
n = 99
# 피보나치 수열 보텀업 다이나믹 프로그래밍으로 구현
for i in range ( 3 , n + 1 ):
dp [ i ]= dp [ i - 1 ]+ dp [ i - 2 ]
print ( dp [ n ])
탑다운 방식은 '하향식' 이라고도 하며, 보텀업 방식은 '상향식'이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블' 이라고 부르며, 메모제이션은 탑다운 방식에서 사용되는 표현이다.
메모제이션은 이전의 계산 결과를 일시적으로 기록해 놓는 넓은 개념이이다. 한 번 계산된 결과를 어디에 기록만하고 활용하지 않을 수도 있기 때문에 엄밀히 말하자면 다이나믹프로그래밍과 메모제이션은 별도의 개념이다.
또한 수열을 배열이나 리스트로 표현할 수 있다고 하였는데 메모제이션은 때에 따라 다른 자료형, 예를들면 사전(dict)자료형을 이용할 수도 있다. 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용하다.
예를들어 f(n)을 계산하고자 할때, f(0)~f(n-1) 모두가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우가 있을 수 있다. 이럴 때는 사전 자료형을 사용하면 효과적이다.
다이나믹 프로그래밍 유형의 문제를 푸는 첫번 째 단계는 해당 문제가 다이나믹 프로그래밍 유형임을 파악하는 것 이다. 특정 문제를 완전 탐색 알고리즘으로 접근 하였을 시 시간이 매우 오래 걸린다면 다이나믹 프로그래밍을 적용할 수 있는지 확인하기 위해 부분 문제들의 중복여부를 확인해봐야한다.
그리고 가능하다면 재귀함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는것이 권장된다. 시스템상 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 위 피보나치 수열의 n값을 5000으로 설정하면 '재귀 함수 깊이'와 관련된 오류가 출력된다.( 물론 sys라이브러리의 setrecursionlimit 함수를 호출하여 제귀 제한을 완화하는게 가능하긴하다.)
from http://20210916start.tistory.com/91 by ccl(A) rewrite - 2021-10-01 06:27:56