[Algorithm] 다이나믹 프로그래밍(DP) - 탑다운, 바텀업

컴퓨터의 연산 속도에는 한계가 있고 그 속도를 단축 시켜줄 방법이 필요합니다. 연산속도와 메모리 공간을 효율적으로 활용할 수 있는 알고리즘 방법이 있습니다.

 

다이나믹 프로그래밍 우리말로는 동적 계획법이라고 불리우는 알고리즘입니다. 다이나믹 프로그래밍을 이용하여 풀 수 있는 문제를 알아보겠습니다.

 

피보나치 수열 : 인접 한 두 수를 더해서 다음 수를 구하는 수열

 

1 1 2 3 5 8 13 21 34 55 89.... 

 

피보나치 수열 코드

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

 

결과)

55

 

10을 수행하는데 시간이 조금 걸린다. 더 빠르게 수행하기 위해 다이나믹 프로그래밍을 사용할 수 있다.

 

f(3)이 여러번 호출되는 것을 알 수 있는데 다이나믹 프로그래밍의 메모이제이션을 이용하면 호출횟수를 줄여서 속도를 높일 수 있습니다.

 

큰 문제를 작은 문제로 나누고 작은 문제는 큰 문제에서도 동일한 값을 가집니다.

 

피보나치 수열 재귀적방법(탑 다운)

dp = [0]*100

def fibo(n):
    if n == 1 or n == 2:
        return 1
    if dp[n] != 0:
        return dp[n]
    dp[n] = fibo(n-1) + fibo(n-2)
    return dp[n]
print(fibo(99))

 

결과)

218922995834555169026

 

dp를 사용하니 금방 결과가 출력되었습니다.

 

이렇게 재귀함수를 이용하여 큰 문제에서 작은 문제의 값을 찾아가서 다시 되돌아오는 방식을 탑다운(top-down) 방식이라고 부릅니다. 다른 말로 하향식이라고도 부릅니다.

 

하지만 재귀함수 대신 반복문을 사용하여 dp를 구현하는 경우가 있습니다. 이런 경우를 바텀업(bottom-up) 방식이라고 부릅니다.

 

반복문을 사용한 방식이 재귀함수를 사용한 방식보다 성능이 조금 더 좋다고 합니다. 피보나치 수열로 알아보겠습니다.

 

피보나치 수열 반복적방법(바텀업)

dp = [0]*100 #1
n = 99
dp[1] = 1
dp[2] = 1
for i in range(3, n+1):
    dp[i] = dp[i-2] + dp[i-1]
print(dp[n])

 

#1 : 결과 저장용 리스트(DP 테이블)

 

결과)

218922995834555169026

 

작은수 3부터 시작해서 n까지 채워서 올라가는 방식이므로 바텀업(bottom-up) 방식이라고 부릅니다. 다른 말로 상향식이라고도 부릅니다.