[이코테] 다이나믹 프로그래밍

중복되는 연산을 줄이자

- 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 알고리즙을 작성해야 한다

- 어떤 문제는 메모리 공간을 약간만 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있다

- 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming) 기법으로, 동적 계획법이라고도 부른다

- 다이나믹 프로그래밍의 기본 아이디어를 알아보고, 탑다운 방식과 보텀업 방식에 대해 알아보자

- 추가로 다이나믹 프로그래밍을 위해 자주 사용되는 메모이제이션 기법까지 알아보자

 

다이나믹 프로그래밍 - 피보나치 수열 

- 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다

- 피보나치수열은 이전 두 항의 합을 현재의 항으로 설정한다

 

 

- 수학자들은 수열의 항이 이어지는 형태를 점화식을 사용해 간결하게 한다 (점화식: 인접한 항 사이의 관계식)

- 피보나치수열의 점화식은 다음과 같다

- 이렇듯 인접한 3개의 항에 대해 식이 정의된 점화식을 인접 3항간 점화식이라고 부른다

- 피보나치수열에서의 첫 번째 항과 두 번째 항이 모두 1이므로, 최종적으로 피보나치수열은 아래와 같이 정의할 수 있다

- 이를 해석하면 n번째 피보나치 수 = (n-1) 번째 피보나치 수 + (n-2) 번째 피보나치 수라는 의미를 가지며

- 1번째 피보나치 수의 값은 1이고, 2번째 피보나치 수의 값 역시 1이어야 한다는 전제를 만족해야 한다

- 프로그래밍에서는 수열 자체가 여러 수를 규칙에 따라 배열된 형태를 의미하기 때문에,배열이나 리스트로 표현한다

- 그렇다면 이 점화식을 통해 피보나치수열을 구하는 과정을 어떻게 표현해야 할까?

 

- n번째 피보나치 수를 f(n)으로 표현한다면 , 4번째 피보나치 수 f(4)를 구하기 위해 위와 같이 함수 f를 반복해서 호출해야 한다

- 이때, f(1)과 f(2)는 항상 1이기 때문에 f(1)이나 f(2)를 만나면 호출을 정지한다

- 수학적 점화식을 프로그래밍으로 표현하기 위해 재귀 함수를 아래의 예시 코드(8-1)와 같이 사용한다

 

# 8-1.py 피보나치 함수 소스코드
## 피보나치 함수를 재귀를 사용해 구현

def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)
   
print(fibo(4))

- 이와 같은 코드는 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어난다는 문제가 발생한다

- 예를 들어 n = 30 인 경우 약 10억 가량의 연산을 수행해야 한다

- f(6)의 호출 과정을 그림을 통해 확인해보자

 

- 동일한 함수 f(3)이 반복적으로 호출되는 것을 확인할 수 있다. 즉, n이 커지면 커질수록 반복해서 호출되는 수가 많아진다

- 이처럼 단순히 매 번 계산하게 되면 문제를 효율적으로 해결할 수 없다

 

다이나믹 프로그래밍 - 탑 다운, 보텀 업 

- 피보나치수열의 이러한 문제는 아래 조건을 만족한다면, 다이나믹 프로그래밍을 사용해 해결할 수 있다

 

[다이나믹 프로그래밍을 사용하기 위한 조건]
1. 큰 문제를 작은 문제로 나눌 수 있다
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

- 피보나치수열은 이러한 조건을 만족하는 대표적인 문제로, 메모이제이션(Memoization) 기법을 사용해 해결할 수 있다

- 메모이제이션은 한번 구한 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다

- 메모이제이션은 값을 저장해 두고 사용하는 방법이므로, 캐싱(Caching)이라고도 불린다

- 메모이제이션을 실제로 구현하기 위해서는 한번 구한 값을 저장하기 위한 리스트를 생성해 사용한다. 소스코드(8-2)는 아래와 같다 

 

# 8-2.py 피보나치 수열 소스코드(재귀)
## 한 번 계산된 결과를 메모이제이션 하기위한 리스트 초기화
d = [0] * 100

## 피보나치 함수를 재귀로 구현(탑다운)
def fibo(x):
	# 종료 조건(1 or 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))

- 정리하면 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 동일한 문제는 한번만 풀어 문제를 효율적으로 해결하는 알고리즘이다

- 퀵 정렬에서도 큰 문제를 작게 나누는 방법을 사용했지만, 퀵 정렬은 분할 정복 알고리즘으로 분류된다

- 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이 분할 정복 알고리즘과의 차이점이다

 

- 메모이제이션 기법을 사용하면 f(6)를 다시 표시하면 위와 같이 색칠된 노드만 방문하게 된다

- 물론 재귀 함수를 사용하면 함수를 재호출 했을 때 메모리 상에 적재되므로 오버헤드가 발생할 수 있다

- 따라서 재귀 대신 반복문을 사용해 오버헤드를 줄일 수 있다

- 일반적으로 재귀보다 반복문을 이용한 다이나믹 프로그래밍의 성능이 더 좋다

- 다이나믹 프로그래밍을 적용한 피보나치수열 알고리즘의 시간 복잡도는 O(N)이다

- 함수가 종료될 때 어떤 함수를 호출했는지, 현재의 피보나치 수를 출력하도록 소스코드(8-3)를 만들면 아래와 같다

 

# 8-3.py 호출되는 함수 확인

d = [0] * 100

def pibo(x):
	print('f('+str(x)+')', end=' ')
    if x == 1 or x == 2: return 1
    if d[x] != 0: return d[x]
    d[x] = pibo(x-1) + pibo(x-2)
    return d[x]
   
pibo(6)

# 실행 결과
## f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

- 소스 코드(8-3)처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 탑 다운 방식(Top-down)이라 말한다

- 반면 단순 반복문을 사용해 소스코드(8-4)를 작성한다면, 작은 문제부터 차근차근 답을 도출한다고 하여 보텀 업 방식(Bottom-up)이라 한다

 

# 8-4.py 피보나치 수열 소스코드

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

# 피보나치 수열을 반복문으로 구현(Bottom-up방식)
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]
    
print(d[n])

- 탑 다운 방식(메모제이션)은 하향식, 보텀 업 방식은 상향식이라고도 말한다

- 다이나믹 프로그래밍의 전형적인 형태는 보텀 업 방식이다

- 보텀업 방식에서 사용되는 결과 저장용 리스트는 DP테이블이라고 부르며 메모이제이션 방식은 탑 다운 방식으로만 사용할 수 있다

- 메모이제이션은 이전의 계산 결과를 일시적으로 기록해두는 개념으로, 계산 결과를 기록만 해두고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다. 그렇기때문에 다이나믹 프로그래밍과 메모이제이션은 엄밀히 말하면 별도의 개념이다. 

 

참고

- 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제되므로, 교재의 문제를 올바르게 습득하면 큰 어려움이 없을 것이다

- 특정 문제를 먼저 완전 탐색 알고리즘으로 접근했을 때, 시간이 많이 걸린다면 부분 문제의 중복 여부를 확인하자

- 중복되는 작은 문제들을 발견했다면 먼저 탑다운이나 메모이제이션을 적용해 코드를 개선하도록 한다

- 그리고 가능하다면 재귀 함수를 사용하는 탑다운 방식보다는 반복문을 사용하는 보텀 업 방식을 권장한다

- 시스템 상 재귀 함수의 스택 크기가 한정되어 있을 수 있다

- 만약 재귀를 사용했을 때, 재귀 함수 깊이로 인한 recursion depth 관련 오류가 발생한다면  sys 라이브러리에 포함된 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있다