[Algorithm] 다이나믹 프로그래밍이 뭐야?

다이나믹 프로그래밍은 중복되는 연산을 줄이기 위해 메모리 공간을 더 사용하여 연산 속도를 높이는 프로그래밍 기법으로 탑다운과 바텀업 방식이 있다. 한번 연산한 값을 기억해 두었다가 재활용하는 것과 같다.

 

우선 다이나믹 프로그래밍에는 조건이 따른다.

• 문제가 여러개의 작은 문제로 나눠질 수 있어야 한다.
• 문제의 정답을 작은 문제의 정답에서부터 구할 수 있다.

다음은 탑다운 방식과 바텀업 방식 설명이다.

• 탑다운 방식: 큰 문제를 해결하기 위해 작은 문제를 호출하여 해결
• 바텀업 방식: 작은 문제부터 답을 도출하여 문제를 해결

피보나치수열을 예시로 다이나믹 프로그래밍을 설명하겠다. 다음은 재귀 함수를 이용하여 구현한 피보나치 수열이다.

 

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

 

다음은 위의 코드가 거치는 과정을 시각화한 자료이다.

 

재귀 함수를 이용한 피보나치 수열

그림에서 볼 수 있듯이 반복되는 연산이 많이 등장하고 연산의 횟수 또한 많다. 따라서 x의 숫자가 커지면 커질수록 연산의 횟수는 기하급수적으로 늘어나게 된다. 만약 해당 코드로 99번째 피보나치 수열을 구하려고 한다면 죽을 때까지 연산이 끝나지 않을 것이다. 그렇다면 피보나치수열 99번째 수는 구할 수 없는 것인가?

 

다이나믹 프로그래밍을 사용한다면 해결할 수 있다. 해결 방법은 다음과 같다. 최초 1회 계산된 값을 따로 저장해두었다고 중복되는 연산이 나올 때 연산을 진행하지 않고 해당 값을 가져오는 방법을 이용하는 것이다.

 

다음은 [재귀 함수를 이용한 피보나치수열]에서 다이나믹 프로그래밍을 사용하여 연산 횟수를 줄인 것을 시각화한 자료이다. 

 

다이나믹 프로그래밍을 이용한 피보나치 수열 연산

그림에서 볼 수 있듯이 연산 횟수가 많이 줄어든 것을 확인할 수 있습니다.

 

다음을 탑다운 방식으로 코드를 작성하면 다음과 같다.

 

# 탑다운 방식 피보나치 수열
memo = [0] * 100
 
def fibo(x):
  if x == 1 or x == 2:
    return 1
  if memo[x] != 0:
    return memo[x]
  memo[x] = fibo(x-1) + fibo(x-2)
  return memo[x]
 
print(fibo(99))

 

큰 문제 99번째 피보나치를 구하기 위하여 작은 문제(98번째, 97번째 등)들을 호출하여 문제를 해결한다.

 

다음은 바텀업 방식으로 코드를 작성한 것이다.

 

# 바텀업 방식 피보나치 수열
memo = [0] * 100
 
memo[1] = 1
memo[2] = 1
n = 99
 
for i in range(3, n+1):
  memo[i] = memo[i-1] + memo[i-2]
 
print(memo[n])

 

작은 문제 3번째 피보나치부터 연산을 시작하여 큰 문제 피보나치 수열 99번째를 구한다.