다이나믹 프로그래밍

본 글은 나동빈 선생님의 이것이 코딩테스트다 with 파이썬을 기준으로 작성되었습니다.

​

출처 : https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6

 

 

​

· 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

​

· 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

다이나믹 프로그래밍의 구현은 일반적으로 탑-다운과 바텀-업으로 구성된다.

​

· 탑-다운 : 위에서 아래로 (하향식)

바텀-업 : 아래에서 위로 (상향식)

​

· 다이나믹 프로그래밍은 2가지 조건을 만족할 때 사용 가능하다.

​

​

1. 최적 부분 구조 (Optimal Substructure)

​

· 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

​

​

2. 중복되는 부분 문제

​

· 동일한 작은 문제를 반복적으로 해결해야 한다.

​

​

Ex) 피보나치 수열

​

피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산 가능

​

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

 

​

피보나치 수열을 점화식으로 표현하면 다음과 같다.

​

an = an-1 + an-2, a1 = 1, a2 = 1

​

​

점화식 : 인접한 항들 사이의 관계식

​

 

피보나치 수열: 단순 재귀 소스코드

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

print(fibo(4))

 

단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다.

​

재귀 함수를 사용할 경우 이전의 값들이 여러 번 호출되게 된다. (즉, 비효율적인 시간 복잡도를 가지게 된다)

​

​

탑-다운

​

· 메모이제이션(Memoization)

​

· 다이나믹 프로그래밍을 구현하는 방법 중 하나로 주로 탑-다운 형식

​

· 한 번 계산한 결과를 메모리 공간에 메모하는 기법

- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

​

​

탑다운 VS 바텀업

​

 

탑다운(메모이제이션) 방식

 

· 하향식이라고도 함

​

· 구현과정에서 재귀함수를 사용함

​

· 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 해결하여 작은 문제들이 해결되었을 때 큰 문제를 해결할 수 있음.

​

· 그 과정에서 한 번 계산된 결과값을 기록하기 위해서 메모이제이션 기법을 사용함

 

· 피보나치 수열: 탑다운 다이나믹 프로그래밍

 

#dp 테이블
dp = [0]*100

#피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    
    if dp[x] != 0:
        return dp[x]

    dp[x] = fibo(x-1) + fibo(x-2)
    return dp[x]

print(fibo(99))

​

바텀업 방식

​

· 상향식이라고도 함

​

· 구현과정에서 반복문을 사용함

​

· 아래쪽에서부터 작은 문제를 하나씩 해결해 나가면서 먼저 계산했던 문제들을 활용해서 다음 문제를 차례대로 해결함.

​

· 다이나믹 프로그래밍의 전형적인 형태

 

피보나치 수열: 바텀업 다이나믹 프로그래밍

​

#dp 테이블
dp = [0]*100

# 첫 번째와 두 번째 피보나치 수를 1로 만듬
dp[1] = 1
dp[2] = 1
n = 99

#피보나치 함수를 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]
    
print(dp[n])

 

 

즉, 두 방법 모두 큰 문제를 여러 개의 부분 문제들로 나누어 풀지만,

​

· 탑-다운은 가장 큰 문제를 방문 후 작은 문제를 재귀적으로 호출하여 답을 찾는 방식이고,

​

· 바텀-업은 반복문을 통해 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식이다.

​

​