DP(다이나믹 프로그래밍)에 대해 알아보자

다이나믹 프로그래밍을 설명할때 빠지지 않는 수열이 있다.

바로 피보나치 수열이다.

피보나치 수열을 3가지 방식으로 접근하여 DP에 대해 알아보자.

우선, 피보나치 수열이란 이전 두 항의 합으로 현재의 항을 구할 수 있는 수열이다.

(단, 1,2 번 째는 정해져있다. F(1) = 1, F(2) = 1)

// n번째 피보나치 수를 구하는 경우
F(n) = F(n-1) + F(n-2)

 

5번째 항을 구하는 경우에는 위 식을 활용하여, F(5) = F(4) + F(3) 으로 구할 수 있다.

왜 피보나치수열을 가장 많이 예시로 들까?

피보나치 수열은 아래의 조건을 가장 직관적이게 만족하는 수열이기 때문이다.

DP 문제는 대부분 아래의 조건을 만족한다.

 

1. 큰 문제를 작은 문제로 구할 수 있을 때
2. 작은 문제는 더 작은 문제로 구할 수 있을 때

 

결론적으로 DP 문제는 F(n)을 구한다고 했을때 F(n-1), F(n-2) 와 같은 값들과 같이 이전 값을 활용하여

구할 수 있을 때 DP 문제일 확률이 높다. 위 식을 이용하여 코드를 바로 짜보자.

언어와 상관없이 식을 바로 적용하여 구하면 된다.

 

def get_current_fibo(n):
  if n==0:
    return 0
  elif n==1:
    return 1
  else:
    fibo_num = get_current_fibo(n-1) + get_current_fibo(n-2)
    return fibo_num

print(get_current_fibo(7))

 

단순하게 식만 활용한 코드이다. 근데 안타깝게도 문제가있다.

위 코드는 N이 커질수록 기하급수적으로 수행시간이 늘어난다는 문제가 있다.

피보나치 문제에 위 코드를 제출하면 분명 메모리 초과로 패스할 수 없을 것이다.

따라서 우리는 위 코드를 개선해야한다.

 

어떻게 개선 할 수 있을까?

 

5번째 항을 구하는 경우는 F(5) = F(4) + F(3) 으로 구할 수 있다고 하였다.

F(4) 는 다시 F(3) + F(2)로 구할 수 있다.

따라서 우리는 F(5)를 구하기 위해, F(4) 와 F(3)을 각각 구해야 값을 찾을 수 있으며

F(5)를 구하기 위해 아래와 같이 식을 표현 해 볼 수 있다.

 

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2)+ F(1)

 

중복된 코드가 보인다.

 

DP는 이러한 중복된 코드를 없애 메모리를 확보하고 빠른 시간안에 답을 구할 수 있게 하는 것이다.

두가지 방법을 이용하여 위 코드를 개선해보자.

 

1. Top Down

 

이름 그대로 위에서부터 아래로 값을 구하는 방식이다.

F(n)을 구할 경우 F(n)부터 차례대로 F(n-1), F(n-2)를 구한다.

# F(0) 은 0이다. 대부분 DP 문제는 초기값이 1 이상이다. 0으로 주어도 무방하다.
# 초기값을 세팅한다.
dp = [0] * 1000
dp[0] = 0
dp[1] = 1

def get_top_fibo(n):
  if n == 0:
    return dp[n]
  elif n == 1:
    return dp[n]
  else:
    dp[n] = get_top_fibo(n-1) + get_top_fibo(n-2)
    return dp[n]

print(get_top_fibo(7))

 

2. Bottom Down

F(n)을 구할 경우 F(1) 부터 차례대로 값을 구한다.

dp = [0] * 1000
dp[0] = 0
dp[1] = 1

def get_bottom_fibo(n):
  if n == 0:
    return dp[n]
  elif n == 1:
    return dp[n]
  for i in range(2,n+1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[i]

print(get_current_fibo(7))

 

보통의 경우 Top Down 방식보다 Bottom Up 방식을 추천한다.

Top Down 방식의 경우 재귀 함수 깊이 관련 에러가 뜰 수 있기 때문이다.

DP 문제를 풀때엔 위와 같이 F(0)부터 차례대로 구해 F(n) 을 구할 수 있는 Botto Up 방식의 코드를 짤 수 있도록

습관을 들이자. (간단하게 말해 작은값 부터 시작하는 루프를 돌려 값을 구하면 된다.)