동적 계획법(Dynamic Programming, DP)이란?
동적 계획법이란 하나의 큰 문제를 여러 개의 작은 부문제로 나누고, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기법이다.
동적 계획법 vs 재귀적 호출
재귀적 호출
일반적인 재귀 방식은 동적 계획법과 매우 유사하다. 단, 재귀를 사용 시 동일한 작은 문제가 여러 번 반복되어 비효율적인 계산이 이루어진다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 각 항을 구하기 위해 f(1), f(0)이 등장할 때까지 계속해서 반환하고, 더하는 작업을 진행한다. 또한 값을 따로 저장해두지 않기 때문에 이전에 구했던 값을 다시 처음부터 계산한다. 이러한 계산 방식 때문에 구하는 항이 증가함에 따라 계산 횟수가 기하급수적으로 늘어난다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1
f(2) = f(1) + f(0)
f(3) = f(2) + f(1) = {f(1) + f(0)} + f(1)
f(4) = f(3) + f(2) = {f(2) + f(1)} + {f(1) + f(0)} = {(f(1) + f(0) + f(1)} + {f(1) + f(0)}
...
동적 계획법
한 번 구한 작은 문제의 값들을 저장해 두고 재사용한다면 어떨까? 하는 해결 방법이 동적 계획법이다. 동적 계획법은 계산 결과를 저장하고, 필요할 때 해당 값을 가져와 재사용한다. 이는 재귀적 호출에서의 중복 계산을 방지하고 속도를 향상할 수 있다.
동적 계획법 적용 조건
중복되는 부분 문제(Overlapping Subproblems)
동적 계획법은 기본적으로 문제를 작게 나누고, 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제가 반복하여 나타나는 경우에 사용이 가능하다.
최적 부분 구조(Optimal Substructure)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다. 예를 들어 아래의 그림을 에서 A - B까지의 가장 짧은 경로를 찾는다고 해보자. A - X(부분 문제)의 경로에서 가장 짧은 경로는 AX2이며, X - B(부분 문제)의 경로에서 가장 짧은 경로는 BX2이다. 해당 부분 문제들의 최적 경로가 A - B의 경로에서 가장 짧은 경로가 되므로, 최적 부분 구조라고 할 수 있다.
동적 계획법 활용하기
문제를 해결하는데 순서가 꼭 정해진 것은 아니지만, 다른 사람들의 여러 가지 활용법 중에서 가장 세분화돼 있는 방법을 정리해 보았다. 총 6단계로 구성돼 있고, 순서는 다음과 같다. 한 단계씩 알아보도록 하자.
- 동적 계획법이 적용 가능한지 파악
- 문제의 변수 파악
- 변수 간 관계식(점화식) 만들기
- 메모하기(Memorization)
- 기저 상태 파악하기
- 구현하기
동적 계획법이 적용 가능한지 파악
동적 계획법 적용 조건에도 적었듯이 '중복되는 부분 문제'와 '최적 부분 구조'를 갖고 있는 문제인지 확인해야 한다. 즉, 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지 판단해야 한다.
문제의 변수 파악
동적 계획법은 현재 변수에 따라 결과 값을 찾고 저장하여 재사용하는 과정을 거친다. 따라서 문제 내 변수를 알아내야 한다. 예를 들어 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 또한 잘 알려진 Knapsack 문제에서는 index, 무게로 2개의 변수를 사용한다. 이처럼 해당 문제에서 어떤 변수가 있는지를 파악해야 답을 도출할 수 있다.
변수 간 관계식(점화식) 만들기
변수들에 의해 결과 값이 달라지지만 동일한 변수 값인 경우 결과는 동일하다. 우리는 그 결과 값을 그대로 이용할 것이므로 관계식을 만들어낼 수 있어야 한다. 그러한 식을 점화식이라고 부르며, 우리의 코드에서 반복/재귀를 통해 문제가 해결되도록 구축할 수 있게 된다. 예를 들어 피보나치 수열에서의 점화식은 f(n) = f(n-1) + f(n-2)이다.
메모하기(Memorization)
결과가 나올 때마다 배열 내에 저장할 수 있도록 변수 값에 따른 결과를 저장할 배열 등을 미리 생성한다. 결과 값을 저장할 때는 보통 배열을 쓰며, 변수 개수에 따라 1~3차원 등으로 다양해진다.
기저 상태 파악하기
이제 가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 손으로 직접 테스트하여 구성하는 경우가 많다. 예를 들어 피보나치 수열에서는 f(0) = 0, f(1) = 1이다. 이를 파악한 뒤 생성했던 배열에 미리 저장해두면 된다. 피보나치 수열의 경우 간단하지만, 문제에 따라 복잡해질 수 있다.
구현하기
동적 계획법은 두 가지 방식으로 구현이 가능하다. 상향식 접근(Bottom-up)과 하향식 접근(Top-down)이다.
상향식 접근(Bottom-up)과 하향식 접근(Top-down)
상향식 접근(Tabulation 방식) - 반복문 사용
상향식 접근은 아래에서부터 계산을 수행 및 누적시켜 전체의 큰 문제를 해결하는 방식이다. 이를 위해 반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열에 저장한다. 일반적으로 직관적으로 이해하기 쉽고, 모든 부분 문제를 해결하므로 최적 부분 구조를 보장한다.
하향식 접근(Memorization 방식) - 재귀 사용
큰 문제를 작은 부분 문제로 나누어 해결하는 방식이다. 이를 위해 재귀 함수를 사용하여 문제를 작은 부분 문제들로 쪼개고, 중복 계산을 피하기 위해 계산한 값을 저장하는 Memoriaztion을 활용한다. 이 방식은 재귀를 사용하므로 구현이 더 간단할 수 있으나 호출 과정에서 오버헤드가 발생할 수 있고, 모든 부분 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 않을 수 있다.
피보나치 수열 적용(Python)
상향식 접근을 활용하여 피보나치 수열을 구현해 보도록 하자.
def bottom_up(n):
fibo = [0, 1] + [0 for i in range(n - 1)]
for i in range(2, n + 1):
fibo[i] = fibo[i - 1] + fibo[i - 2]
return fibo[n]실행 시간을 확인해 봤을 때, colab 환경에서 n = 50이면 0.007초밖에 걸리지 않았다. n = 100000일 때, 0.478초가 걸렸다. 그러나 n을 백만 단위로 진행했을 때, 배열의 크기가 너무 커져서 세션이 다운되는 현상이 발생했다. 변수 값이 증가함에 따라 배열의 크기도 증가하기 때문에 발생하는 현상이다.
import time
s = time.time()
bottom_up(50)
e = time.time()
print(e - s)참고링크
알고리즘 - Dynamic Programming(동적 계획법)
https://hongjw1938.tistory.com/47
동적계획법(Dynamic Programming)
https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming
