[06] 동적 프로그래밍

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문에 연산 속도와 메모리 공간을 최대한 활용하는 효율적인 알고리즘이 필요하다.

=> 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다.

== 다이나믹 프로그래밍 (Dynamic Programming) 기법

 

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

프로그래밍에서는 이러한 수열을 배열 혹은 리스트로 표현.

'연속된 많은 데이터'를 처리하기 때문

파이썬: 리스트 자료형 / C, 자바: 배열

 

피보나치 함수 코드로 표현

# 피보나치 함수를 재귀 함수로 구현

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

 

피보나치 수열에서 f(n)을 호출할 때, n이 늘어날수록 반복해서 호출하는 수가 많아진다.

 

 

다이나믹 프로그래밍이 사용 가능한 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

위의 피보나치 수열은 메모이제이션(Memoization) 기법을 사용해서 해결할 수도 있다.

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

캐싱(Caching): 값을 저장하는방법

 

메모이제이션을 이용한 피보나치 코드

#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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(100))

 

즉, 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다.

(큰 문제를 작게 나누는 점이 퀵 정렬과 비슷하다.)

 

 

반대로,

단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다.

동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결하는 것이다.

 

보텀업 방식을 사용한 피보나치 수열

#앞서 계산된 결과를 저장하기 위한 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테이블이라고 한다.

 

메모이제이션은 때로 사전(dict) 자료형을 이용할 수도 있다.

일부의 작은 문제에 대한 해답이 필요한 경우가 예시이다.

 

 

동적 프로그래밍 유형임을 파악하는 법

: 특정 문제를 완전 탐색 알고리즘으로 접속했을 때 시간이 매우 오래 걸린다면

동적 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인

 

 

시스템 상의 재귀 함수 스택 크기가 한정되어 있을 수 있기 때문에 보텀 업 방식으로 구현하는 것이 권장된다.

 

위의 재귀 피보나치 소스코드에서 5,000 이상의 값을 넣게 된다면 recursion depth 오류가 발생할 수 있다.

 

이 경우 sys 라이브러리의 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있다.