동적 계획법 (Dynamic Programming, DP)

 

1. 정의

큰 문제를 여러개의 작은 문제로 나누어서 작은 문제를 한 번만 풀고 그 결과를 저장해두는 방식

즉, 같은 문제를 여러번 반복하지 않고 한 번 푼건 기억해서 재활용하는 방식

---

2. 쓰는 곳

최적화 문제 (가장 큰 값, 최소비용 찾을 때)

문제를 작게 쪼갤 수 있고 중복되는 계산이 자주 일어날 때 효과적이다

---

3. 핵심 개념

하위 문제 : 큰 문제를 나눈 작은 문제

테이블 또는 Memoization : 계산한 결과를 저장해두는 공간 

Bottom-up 방식 : 작은 문제부터 차례대로 해결해 가는 방식

---

4. 설계 절차 4단계 

1. 해결 방법의 구조를 파악한다

문제를 작은 문제로 나눌 수 있는지

 

3. 재귀적으로 정의한다

예를 들어 f(n) = f(n-1) + f(n-2) 처럼 큰 문제를 이전문제의 해로 표현할 수 있어야 한다

 

4. 반복문으로 계산한다

작은 문제부터 순서대로 계산해서 저장한다

 

5. 필요하면 실제 해답을 구성한다 

최댓값만 구하는 게 아니라 어떤 선택을 했는지도 알기 위해

 

예를 들면 피보나치 수열이 있다 

F(n) = F(n-1) + F(n-2) 

일반 재귀방식 시 중복 계산이 많아서 느리지만

DP방식 시 순서대로 F(1), F(2)...계산해서 저장하면 훨씬 빠르다 

 

---

5. DP를 사용해서 이항계수를 효율적으로 구하기

 

5.1. 이항계수?

n개중에서 k개를 고르는 경우의 수 

 

공식으로는 

C(n, k) = n! / (k!(n-k)!) 

 

하지만 팩토리얼 계산이 느릴 수 있으니 재귀적으로 정의된 식을 활용해서 동적으로 계산한다 

 

C(n, k) = C(n-1, k-1) + C(n-1, k) 
(단, C(n, 0) = C(n, n) = 1)

---

5.2. python 코드

 

입력: 음이 아닌 정수 쌍 
출력: 이항계수 의 값

binomialCoef(n, k):
    C = [[0 for x in range(k+1)] for x in range(n + 1)]
    for i in range(n + 1): 
        for j in range(min(i, k) + 1): 
            if j == 0 or j == i: 
                 C[i][j] = 1
            else: 
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j] 
    return C[n][k]

 

 

1. 중복 계산을 피하기 위해 표에 저장

2. 작은 문제부터 차례대로 계산해서 올라간다 (bottom-up)