[이코테] 다이나믹 프로그래밍(Dynamic Programming)

중복되는 연산 줄이기

• 탑다운
• 보텀업

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. ex) 1 1 2 3 5 8 13 21 34 55 89...

수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다.

피보나치 수열

#재귀 함수를 이용한 피보나치 구현
def fibo(x):
	if x == 1 or  x == 2:
    	return 1
    return fibo(x-1)+fibo(x-2)
print(fibo(4))

 

하지만 피보나치 수열의 코드를 이렇게 작성하면 심각한 문제가 생길 수  있다. 바로 f(n)에 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다.

 

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.

 

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

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

 

이 문제를 메모이제이션(Memoization)기법을 사용해서 해결해보자. 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션 값을 저장하는 방법으로 캐싱(Cashing)이라고도 한다.

 

#메모이제이션(cashing)을 이용한 피보나치의 수
#한 번 계산된 결과를 메모제이션하기 위한 리스트 초기화

d = [0]*100

def fibo(x):
  #종료 조건 1 혹은 2일 때
  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 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.