✏️ 서론
오늘은 동적계획법(dynamic_programming)에 대해 배워보자.
✏️ 본론
📍 dynamic_programming(다이나믹 프로그래밍)
다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시키는 방법으로, 동적 계획법이라고도 표현한다.
동적계획법으로 해결 할 수 있는 대표적인 예제는 피보나치수열이다.
우리는 점화식을 통해 동적계획법으로 코드를 작성할 수 있다.
다음 피보나치 수열의 점화식을 살펴보자.
a(n) = a(n-1) + a(n-2), a1 = 1, a2 = 1
이를 해석하면 다음과 같다.
- n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
- 단, 1, 2번째 피보나치 수 = 1
수학적 점화식을 프로그래밍으로 작성하면 다음과 같이 작성할 수 있다.
def fibo(x):
if x == 0 or x == 1:
return 1
return fibo(x-1) + fibo(x-2)그런데, 이런식으로 소스코드로 작성하면 심각한 문제가 생길 수 있다. 바로 f(n) 함수에서 n이 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다.
이 소스코드의 시간 복잡도를 말하면 O(2^n)의 지수시간이 소요된다고 표현한다.
만약, n = 30이라고 가정하면 약 10억가량의 연산을 수행해야하는데, 이는 매우 비효율적이다.
이처럼, 점화식을 재귀함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록하면 문제를 효율적으로 풀 수 없다.
이러한 문제는, 다이나믹 프로그래밍을 사용하면 효율적으로 해결 할 수 있는데, 다음의 조건이 필요함을 인지하자
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 문제는 이러한 조건을 만족하는 대표적인 문제이다.
⚡️ 메모이제이션(top_down)
이 문제는 메모이제이션(memoization)을 통해서도 풀 수 있는데,
메모이제이션(memoization)이란, 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 일명 캐싱(caching) 이라고도 한다.
코드는 다음과 같다.
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
memo = [0] * 101
# 피보나치 함수를 재귀함수로 구현(top_down)
def fibo(x):
if x == 1 or x == 2:
return 1
if memo[x] != 0:
return memo[x]
memo[x] = memo[x-1] + memo[x-2]
return memo[x]
print(fibo(100))⚡️ for문(bottom_up)
재귀적인 방법을 사용하게 되면, 함수를 다시 호출했을 때 메모리상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생 할 수 있다. 따라서, 재귀 함수 대신 반복문을 사용하여 오버헤드를 줄일 수 있다.
일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다.
memo = [0] * 101
n= 99
memo[1] = 1
memo[2] = 1
for i in range(3, n+1):
memo[i] = memo[i-1] + memo[i-2]
print(memo[n])📍 정리
정리하자면, 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
이는, 퀵 정렬(quick_sort)와도 비슷한 기법인데 자세히 들여다보면 둘의 차이점이 있다.
퀵 정렬은 한번 pivot이 자리를 변경해 기준을 잡게 되면 해당 기준은 바뀌지 않고 그 피벗값을 다시 처리하는 동작이 없으나 (return quick_sort(left) + [pivot] + quick_sort(right))
다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결하는 점이 두 함수의 차이점이다.
즉, 이미 해결이 됐으니 결과를 어딘가에 저장해놨다가 나중에 동일한 문제가 생기면 이미 저장한 값을 반환하는 것이다.
가능하다면 재귀 함수를 이용하는 top_down 방식보다는 bottom_up방식으로 구현하는 것을 권장한다.
시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.
만약, 재귀함수를 사용하다가 recursion depth(재귀 함수 깊이) 오류가 뜨면, sys - setrecursionlimit() 를 호출하도록 하자.
✏️ 결론
이렇게해서 다이나믹 프로그래밍의 전반적인 개념을 배웠다.
딱 배우고 드는 생각은 아. 이거 어렵다😂 😂라는 생각이다.
많은 문제를 풀어보면 좀 나아지려나?
한번 문제를 풀어보자.
