DP (Dynamic Programming)란
다이나믹 프로그래밍(=동적 계획법)의 기본적인 아이디어는 하나의 복잡한 문제를 간단한 하위 문제 여러 개로 나누어 해결하는 알고리즘 기법이다. 각 하위 문제의 해결 방법을 저장하고, 동일한 하위 문제가 발생했을 때 이를 다시 계산하지 않고 저장된 값을 활용함으로써 효율적으로 문제를 해결할 수 있다.
동적 계획법은 하나의 문제를 여러 개의 하위 문제로 나누어 해결한다는 접에서 분할 정복(Divide and Conquer)과 유사하다. 그러나 동적 계획법은 분할된 부분문제들끼리 서로 의존적이지만 분할 정복은 부분문제들끼리 서로 독립적이라는 차이점을 갖는다.
DP 적용 조건
다이나믹 프로그래밍을 적용할 수 있는 상황에 대한 조건은 다음과 같다.
- 최적 부분구조 (Optimal Substructure)
: 부분 문제의 최적 값을 통해 전체 문제의 최적 값을 도출할 수 있는 구조- 중복되는 부분문제 (Overlapping Subproblems)
: 전체 문제를 해결함에 있어 동일한 부분 문제가 중복되어 발생하는 문제
예제) 피보나치 문제
대표적으로 피보나치 문제에 DP를 적용할 수 있다.
1. 재귀적 방법
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)점화식처럼 관계식이 주어져있기 때문에 재귀로 구현할 수 있다.
재귀적 방법으로 f(5)를 구할 때, f(4)와 f(3)을 계산해야 한다. 이 때 f(4)를 구하기 위해서는 다시 f(3)과 f(2)를 계산해야 한다. 이 때 f(3)은 이전에 계산되었기 때문에 다시 계산할 필요가 없지만 재귀적 방법에서는 이를 고려하지 않고 모든 하위 문제를 매번 다시 계산하게 된다. 이로 인해 중복 계산이 발생해 불필요한 연산 횟수가 많아지게 된다.
재귀적 방법으로 구현 시 f(n)을 위해 O(2^n)의 시간 복잡도를 가지며, 이는 n값에 비례해 연산량이 급격히 증가함을 확인할 수 있다.
2. 동적 계획법
f(n)은 f(n-1)과 f(n-2)의 합으로 구성되어 최적 부분구조 조건(부분문제의 값만으로 전체문제의 값을 구할 수 있음)을 만족한다.
또한 f(5)를 구하기 위해 위 그림과 같이 f(4), f(3), .., f(0)의 똑같은 부분문제가 계속 발생됨을 알 수 있다. 즉 중복되는 부분문제를 만족한다.
def fibonacci(n):
fib = [0] * (n+1)
fib[1] = 1
for i in range(2, n+1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]따라서 동적 계획법을 위한 조건이 성립되어 적용해 구현할 수 있다. 반복문을 통해 각 항의 값을 저장하면서 이전 값들을 활용해 새로운 값을 계산하여 중복 계산을 피하고, 이전에 계산된 값을 재활용함으로써 효율적으로 연산할 수 있다.
일반적으로 DP 적용 시 부분문제의 값을 알고 있을 때 O(1)이 소요되며, 모든 부분문제의 개수는 n이므로 O(n)의 시간 복잡도를 갖는다.
DP 적용
동적 계획법은 어떤 특정 경우에만 적용되는 것이 아닌 다양한 문제 해결에 적용할 수 있는 알고리즘이기에 풀고자 하는 문제가 동적 계획법을 사용할 수 있는 문제인지 확인하는 과정이 필요하다.
먼저 앞선 최적 부분구조/중복되는 부분문제 조건을 만족하여야 한다. 그리고 문제에서 사용할 변수에 대해 정의하고 변수 간 관계식(점화식)을 수립한다. 이후 계산될 때마다 배열에 값을 저장하고 이를 재사용하는 방식으로 문제를 해결한다.
구현 방법은 크게 상향식과 하향식, 두 방법으로 나뉜다.
-
상향식 방법 (Bottom-up, Tabulation) - 반복문 사용
작은 문제에서 시작해 누적시켜 점진적으로 큰 문제를 해결하는 방식이다. 결과를 저장한 배열 dp[0]에서 시작해 목표인 dp[n]에 이르기까지 값을 저장하며 이를 재활용하며 진행된다. -
하향식 방법 (Top-down, Memoization) - 재귀 사용
dp[0]처럼 처음부터 출발하는 게 아닌 dp[n]을 구하기 위해 위에서 시작해 dp[0]까지 내려간 다음 결과 값을 재귀를 통해 재활용하는 방식이다. 큰 문제를 해결할 때 부분문제가 해결되지 않았다면 그제서야 해결하게 된다.
