✅ 동적 계획법이란?
ㅇ 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고, 다시 큰 문제를 해결할 때 사용하는 것.
ㅇ 즉, 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다.
ㅇ 동적 계획법은 다이나믹 프로그래밍(DP) 라고도 불린다.
✅ 동적 계획법의 조건
1️⃣ 최적 부분 구조
ㅇ 부분 문제의 최적 결과 값을 사용하여 전체 문제의 최적 결과를 낼 수 있는 경우.
ㅇ 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다는 특징이 있음.
ㅇ 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2)으로, 위와 같은 트리구조로 함수가 호출되게 된다. 위 그림에서도 쉽게 찾을 수 있듯이 fib(1), fib(2), fib(3)과 같이 동일한 부분 문제가 중복되어 나타나는 것을 볼 수 있다.
2️⃣ 중복된 하위 문제 (겹치는 부분 문제)
ㅇ 동적 계획법은 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용하여 전체 답을 구하기 때문에, 동일한 작은 문제들이 반복하여 나타나는 경우에 사용할 수 있다.
ㅇ 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하여 사용할 수 없다.
❔그렇다면 동적 계획법은 언제 사용해야 하는가❔
1️⃣ 동적 계획법으로 풀 수 있는 문제인지 확인하기
ㅇ 해당 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지 확인해야 한다.
ㅇ ex) 특정 데이터 내 최대화/최소화 계산
ㅇ ex) 특정 조건 내 데이터 개수 세는 문제
ㅇ ex) 확률 등의 계산
2️⃣ 문제의 변수 파악하기
ㅇ 동적 계획법은 현재 변수에 따라 그 결과 값을 찾고, 그것을 전달하여 재사용하는 과정을 거치기 때문에 문제 내 변수의 개수를 알아내야 한다.
ㅇex) 피보나치 수열 : 변수(n)
3️⃣ 변수 간 관계식 세우기 (점화식)
ㅇ 점화식을 구축하여 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결될 수 있도록 한다.
ㅇ ex) 피보나치 수열 : f(n) = f(n-1) + f(n-2)
4️⃣ 메모하기 (Memoization)
ㅇ 변수 값에 따른 결과를 저장할 배열 등을 미리 만들어둔다.
ㅇ 결과가 나올때마다 배열에 저장하여 재사용하는 방식으로 문제를 해결해 나간다.
5️⃣ 기저 상태 파악하기
ㅇ 가장 작은 문제의 상태를 알아내야 한다.
ㅇ 보통 몇 가지 예시를 직접 테스트하여 구성하는 경우가 많다.
ㅇ 해당 기저 문제에 대해 파악한 후 배열 등에 저장해두면 된다.
ㅇ ex) 피보나치 수열 : f(0) = 0, f(1) = 1, f(2) = 1과 같은 방식
6️⃣ 구현하기
ㅇ DP를 구현할 때는 총 2가지의 방법을 사용할 수 있다.
ㅇ Bottom-Up(상향식) - Tabulation 방식이라고도 불리며 반복문을 사용한다.
ㅇ Top-Down(하향식) - Memoiation 방식이라고도 불리며 재귀를 사용한다.
◻ Bottom-Up 방식
ㅇ 아래에서 부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.
ㅇ 재귀 호출을 사용하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다.
ㅇ dp[0]이 기저 상태이고 dp[n]이 목표 상태라고 할 때, Bottom-up 방식은 dp[0] 부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n] 까지 그 값을 전이시켜 재활용하는 방식이다.
ㅇ 반복을 통해 하나씩 채우는 과정을 "table-filling" 이라고 하는데, Bottom-Up 방식은 이 테이블에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다. (재활용 측면에서 메모이제이션과 크게 다르지 않음)
num = int(input())
def fibonacci(num):
dp = [0]*(num+1)
dp[0] = 0
dp[1] = 1
for i in range(2, num+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp)
return dp[num]
print(fibonacci(num))
◻ Top-Down
ㅇ dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위하여 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결괏값을 재귀를 통해 전이시켜 재활용하는 방식
ㅇ 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 되기 때문에, 메모이제이션(Memoization) 이라고 부른다.
num = int(input())
dp = [0]*(num+1)
dp[1] = 1
dp[2] = 1
def fibonacci(num):
if dp[num] == 0:
dp[num] = fibonacci(num-1) + fibonacci(num-2)
return dp[num]
print(fibonacci(num))
✅ 동적 계획법(DP) vs 그리디
ㅇ 그리디 알고리즘
- 현 상태에서 가장 최적의 경우를 판단하여 결정한다.
- 따라서 도출된 값이 항상 최적의 해라고는 할 수 없다.
ㅇ 동적 계획법(Dynamic Programming)
- 모든 가능성을 고려하여 항상 최적의 결과를 도출한다.
- 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있다.
✅ 동적계획법(DP) vs 분할 정복
ㅇ 동적 계획법과 분할 정복의 공통점은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
= 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우
ㅇ 동적 계획법은 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복되는 반면, 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
ㅇ 분할 정복의 예시 : 퀵 정렬, 병합 정렬
ㅇ 동적 계획법 예시 : 피보나치수열
[REFERENCE]
https://hongjw1938.tistory.com/47
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으
hongjw1938.tistory.com
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)
현실에서 우리가 컴퓨터를 이용하여 문제를 해결하려 할 때 컴퓨터로도 해결하기 어려운 문제들이 있을 것이다. 보통 최적의 해를 구하는데 시간이 매우 오래걸리거나 메모리 공간이 많이 필요
velog.io
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
동적 계획법 - 위키백과, 우리 모두의 백과사전
수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분
ko.wikipedia.org
'알고리즘' 카테고리의 다른 글
| 5. 그리디 알고리즘(Greedy Algorithm) (0) | 2022.04.01 |
|---|---|
| 3. 이진탐색 알고리즘(binary_search) (0) | 2022.03.21 |
| 2. 복잡도(Time complexity) (0) | 2022.03.20 |
| 1. 알고리즘이란? (0) | 2022.03.16 |
