[알고리즘 시리즈] 동적 계획법 : Dynamic Programming

---

동적 계획법 : Dynamic Programming

목차

1. 다이내믹 프로그래밍의 목적

2. 다이나믹 프로그래밍의 적용 절차

3. 다이나믹 프로그래밍의 적용 조건

4. 다이나믹 프로그래밍이 적용된 형태

5. 다이나믹 프로그래밍과 분할 정복의 차이점

6. 다이나믹 프로그래밍을 적용한 대표적인 문제들

---

1. 다이나믹 프로그래밍의 목적

재계산을 피한다.

 

2. 다이나믹 프로그래밍의 적용 조건

1) Optimal Substurcture

부분 문제의 최적의 값으로 전체 문제의 최적의 값을 구할 수 있는가

 

2) Overlapping Subproblems

동일한 부분문제가 반복해서 나타나는가

 

3. 다이나믹 프로그래밍의 적용 절차

1. 전체 문제를 부분 문제로 나눈다.
2. 부분 문제를 해결하고 결괏값을 저장한다.
3. 부분 문제의 답과 해결 방식을 이용하여 전체 문제를 해결한다.

 

4. 다이나믹 프로그래밍이 적용된 형태

1) Tabulation

base부터 DP 테이블을 채워나간다.

# 피보나치 수열의 10번째 수를 출력하라
n = 10
dp = [0 for _ in range(n+1)]
dp[1], dp[2] = 1, 1

for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

 

2) Memoization

재귀적으로 부분 문제를 해결하고 중복되는 부분 문제는 값을 재사용한다.

# 피보나치 수열의 10번째 수를 출력하라
n = 10
dp = [0 for _ in range(n+1)]

def fibonacci(i):
    if(i==1 or i==2):
        return 1
    
    if dp[i] != 0:
        return dp[i]
    
    dp[i] = fibonacci(i-1) + fibonacci(i-2)
    return dp[i]

print(fibonacci(n))

 

5. 다이나믹 프로그래밍과 분할 정복의 차이점

다이나믹 프로그래밍은 문제를 부분 문제로 나누어 해결한다는 점에서 분할 정복과 비슷하다고 평가받는다. 하지만, 이 두 가지 알고리즘은 적용되는 상황이 명확히 다른 알고리즘이다.

부분 문제를 나눌 때 Overlapping Subproblems가 발생하면 다이나믹 프로그래밍을 사용하고, Overlapping Subproblems가 발생하지 않으면 분할 정복을 사용한다.

 

6. 다이나믹 프로그래밍을 적용한 대표적인 문제들

LIS : 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

 

LCS : 최장 공통부분 수열

9251번: LCS (acmicpc.net)

 

냅색 문제 : 정해진 무게 내에 물건들의 가치합의 최댓값을 구하는 문제

12865번: 평범한 배낭 (acmicpc.net)

---