📝Dynamic Programmnig?
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것
특정한 알고리즘이 아닌 하나의 문제해결 패러다임
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용!
1950년, Richard Bellman이 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지었다고 ..
DP를 쓰는 이유? 🧐
일반적인 재귀 방식 또한 DP와 매우 유사하다.
BUT
일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다.
ex) 피보나치 수열
0 1 1 2 3 5 8 13 21 34 55 89 144
-
재귀로 함수를 구성할 경우 -> return f(n)=f(n-1)+f(n-2)
f(n-1),f(n-2)에서 각 함수를 1번씩 호출 -> 동일한 값을 2번씩 구하게 된다.
f(5)를 구하기 위하여 f(1)을 5번이나 호출하는 모습
이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가 -> 컴퓨터도 죽는다.
시간 복잡도 = O(n^2) -
DP로 구성
한번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면?
앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능하다.
즉, 매우 효율적으로 문제를 해결할 수 있게 된다.
시간 복잡도 = O(f(n)) (다항식 수준으로, 문제에 따라 다름)
DP의 사용조건
1. Overlapping Subproblems (겹치는 부분 문제)
2. Optimal Substructure (최적 부분 구조)
- Overlapping Subproblems (겹치는 부분 문제)
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.
동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
- Optimal Substructure (최적 부분 구조)
A에서 X를 거쳐 B로 가는 경우,
A-X 경로 중 2번이 가장 짧은 경로, B-X 경로 중 1번이 가장 짧은 경로라면
2번-1번을 지나가는 것이 A-X-B 경로 중 가장 짧은 경로가 될 것이다.
이와 같이, 부분 문제에서 구한 최적 결과 값이 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용 가능하다.
DP 사용하기
DP는 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있다.
- DP로 풀 수 있는 문제인지 확인
DP 사용조건들이 충족되는 문제인지 체크- 문제의 변수파악
DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다.
ex) 피보나치 -> n번째 숫자를 구하는 것이므로 n이 변수- 변수 간 관계식 만들기
점화식이라고 부르며 이를 통해 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축
ex) 피보나치 -> f(n)=f(n-1)+f(n-2)- 메모하기(Memoization)
변수의 값에 따른 결과를 저장 (보통 배열을 사용)- 기저 상태 파악하기
가장 작은 문제의 상태를 알아야 한다. 기저 문제에 대해 파악 후 미리 저장
ex) 피보나치 -> f(0)=0, f(1)=1- 구현하기
1) Bottom-Up (Tabulation 방식) - 반복문 사용
2) Top-Down (Memoization 방식) - 재귀 사용
💻DP 구현 방법
1. Bottom-Up
아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결dp[0]이 기저 상태이고 dp[n]을 목표 상태라고 하면 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식
💡Tabulation?
반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling"이라고 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다.
사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 메모하기(Memoization)와 크게 다르지 않다.
2. Top-Down 방식
dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여
dp[0]의 상태까지 내려간 다음
해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식 피보나치를 예시로, n=5일 때, f(3),f(2)의 동일한 계산이 반복적으로 나오게 된다.
이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다.
가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.
DP를 사용하여 피보나치 풀기
https://www.acmicpc.net/problem/2748
//Bottom-Up 방식을 사용 (c++)
#include <stdio.h>
#include <iostream>
using namespace std;
int main() {
long long * fibo = new long long[90];
int num;
cin >> num;
fibo[0] = 0;
fibo[1] = 1;
for (int i = 2; i <= num; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
cout << fibo[num];
}