어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.
대표적인 방법이 바로 다이나믹 프로그래밍 기법, 동적 계획법이라고도 한다.
시간 복잡도는 O(n)이다.
다음 조건을 만족할 때 다이나믹 프로그래밍을 사용하면 편하다
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
다이나믹 프로그래밍은 2가지 방식이 있다. 바로 탑다운 방식과, 보텀업 방식이 있다.
대표적으로 DP로 해결할 수 있는 예시는 피보나치 수열이다.
이를 해석하면
- n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
- 단, 1번째 피보나치 수 = 1,2번째 피보나치 수 = 1
재귀함수로 간단하게 표현하면 다음과 같다.
# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))but ! 이렇게 작성하면 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 비효율적이다.
이걸 보면 f(3)이 반복적으로 호출되는 것을 볼 수 있다. f(3)은 총 3번 호출되었다.
이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수 는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수없다. 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수있다.
다만 위에 설명한 것처럼 아래 조건을 만족해야한다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
이 문제를 메모이제이션(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(99))
📌 정리하면, 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
🤔 근데 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 쓰인다. 퀵 정렬은 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복 알고리즘으로 분류된다.
다이나믹 프로그래밍과 퀵 정렬의 차이점은, 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
~다시 다이나믹 프로그래밍 이야기로 돌아와서~
재귀함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출햇을 때 메모리상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.
일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋기 때문이다.
다이나믹 프로그래밍 성능 : 반복문 > 재귀함수
피보나치를 구했을 때 처럼, 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을,
큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(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])탑다운(메모이제이션) 방식은 '하향식'이라고도 하며, 보텀업 방식은 '상향식'이라고도 한다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부른다.
메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
참고로, 3차원 리스트를 이용해야 하는 복잡한 난이도가 출제될 경우엔, 최단 경로의 플로이드 워셜 알고리즘을 찾아보자
가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.
시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문.
recursion depth과 관련된 오류가 발생한다면,sys라이브러리에 포함되어 있는setrecursionlimit()함수를 호출하여 해결하자
📌 문제를 접할 때
그리디, 구현, 완전탐색 등의 아이디어로 해결할 수 있는지 확인.
다른 방법이 생각나지 않을 때, 다이나믹 프로그래밍!!
