다이나믹 프로그래밍

TheSole 2023. 5. 8. 15:52

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.
대표적인 방법이 바로 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현한다.
다이나믹은 "프로그램이 실행되는 도중에 라는 의미"
탑다운 방식과 바텀업 방식

대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.

점화식이란 인접한 항들 사이의 관계식을 의미하는데, 예를 들어 {an}이 있을 때 수열에서의 각 항을 an이라고 부른다고 가정하자. 우리는 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다. 여기서 점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다. 피보나지 수열의 점화식은 다음과 같다.

이러한 점화식은 인접 3항간 점화식이라고 부르는데 인접한 총 3개의 항에 대해서 식이 정의되기 때문이다. 1, 2, 3, ...과 같이 이어지는 등차수열의 점화식은 다음과 같이 표현할 수 있다.

결과적으로 앞서 언급했던 피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때 다음과 같이 정의 할 수 있다.

이를 해석하면 다음과 같다.

n번째 피보나치 수=(n-1)번째 피보나치 수 +(n-2)번째 피보나치 수
단, 1번째 피보나치 수 = 1, 2번째 피보나치 수=1

# 피노나치 함수(Fibonacci Function)를 재귀 함수로 구현
def fibo(x):
  if x == 1 or x == 2:
    return 1
  return fibo(x-1) + fibo(x-2)
print(fibo(4))

하지만 수열의 코드를 이렇게 작성하면 수행 시간이 기하급수적으로 늘어난다.

이미 계산한 f(3)이 3번이나 계산됨

따라서 이러한 문제점을 개선하기 위해 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

다만 다음 조건을 만족해야 한다.

큰 문제를 작은 문제로 나눌 수 있다.
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

위의 문제를 다이나믹 프로그래밍의 메모제이션 기법(한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미, 메모제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.)을 사용해서 풀어보면, 구현하는 방법은 단순히 한 번 구한 정보를 리스트에 저장하고 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에 가져오면 된다.

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100


# 피보나치 함수(Fibonacci Function)를 재귀함수로 구한(탑다운 다이나믹 프로그래밍)
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(99))

cd = [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]

print(pibo(6))
#out: (6)(5)(4)(3)(2)(1)(2)(3)(4)8

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 Top-Down 방식이라고 말한다.
반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식이라고 말한다.

# 압서 계산된 결과를 저장하기 위한 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 테이블" 이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
가능하다면 보텀업 방식으로 구현하는 것을 권장함.