다이나믹 프로그래밍 (Dynamic Programming)

 

📍 다이나믹 프로그래밍(동적 계획법) 
'한 번 계산한 문제는 다시 계산하지 않도록 한다'는 알고리즘으로,

메모리 공간을 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법이다. 

 

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

구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성된다. 

 

 

 

💥 다이나믹 프로그래밍의 '동적' 의미는, 자료구조에서 사용하는 동적 할당(Dynamic Allocation):

프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법과는 다르다. 별다른 의미 없이 사용된 단어이다.

 

 

 

📍 다이나믹 프로그래밍의 조건 

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

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

 

2. 중복되는 부분 문제(Overlapping Subproblem):

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

 

ex) 대표적인 문제로 피보나치 수열 문제가 있다.

피보나치 수열은 다음과 같은 점화식(인접한 항들 사이의 관계식)을 만족하는 수열이다.

 

 

💥 탑다운 방식에서 사용되는 방법은 메모이제이션(memoization)이다.

한 번 계산한 결과를 메모리 공간에 메모하는 기법으로, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 

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

 

메모이제이션을 이용하는 경우, 시간복잡도는 기존:O(2^N) → O(N)으로 줄게 된다.

 

 

 

📍 탑다운(하향식) vs 보텀업(상향식)

• 탑다운(메모이제이션): 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 해결하여 문제를 해결한다.
• 상향식: 아래쪽에서 작은 문제를 하나씩 해결해나가면서, 먼저 계산했던 값을 활용하여 그 다음 문제를 차례로 해결한다.

- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.

 

 

 

📍 다이나믹 프로그래밍 vs 분할 정복

• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
  • 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.
  • 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며, 부분 문제가 중복된다.
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

 

📍 다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이 중요하다.

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한다.

(다른 문제 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍으로 문제를 해결한다.)

 

 

---

 

 

💥 code example (탑다운): 작은 문제 재귀적으로 해결

 

d = [0] * 100 # 한 번 계산된 결과를 memoization하기 위한 list 초기화

def fibo(x): # 피보나치 함수를 재귀함수로 구현 (탑다운)
    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))

 

 

 

💥 code example (보텀업): 먼저 계산했던 값 이용

 

d = [0] * 100 # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화

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])