다이나믹 프로그래밍이란?
다이나믹 프로그래밍(Dynamic Programming)은 다른말로 동적계획법 이라고 합니다. 저도 처음에는 동적계획법을 듣고 왜 동적계획법일까? 했는데 이름 지으신분이 그냥 이 이름이 멋있어서 이렇게 지었다고 하네요...
DP(다이나믹 프로그래밍)알고리즘은 백준 사이트 알고리즘별로 문제풀기에서 가장많은 문제수를 가지고 있어요!
그만큼 종류도 다양하고, 출제빈도도 높습니다.
DP는 작은문제를 풀어서 큰문제를 해결하는 알고리즘입니다.
여기서 주의할점은 작은문제들을 여러번에 걸쳐서 다시 푸는일이 없도록
어딘가에 값을 저장해두고, 필요할 때 그 값만 가져와서 사용한다는 점입니다.
즉, 문제를 여러번 풀지않고 단 한번만 계산을 할 수 있는 거죠.
예) 피보나치 수열
위는 피보나치 수열 fibonacci(n) = fibonacci(n-1)+fibonacci(n-2) 를 이용해 fibonacci(4)를 구하는 과정입니다.
중복된 부분이 보이시나요?
현재 fibonacci(2)를 구하는 과정이 두번 이루어지고 있습니다.
fibonacci(2)를 이미 한 번 계산했음에도 불구하고 다시구하는... 굉장히 비효율적인 행동이죠.
지금은 중복이 한번뿐이지만 숫자가 커질수록 기하급수적으로 중복의 수가 많아지고 이는 시간초과를 일으키게 될 것입니다.
DP는 이런중복계산을 없애줍니다.
이미 구한 값을 다시 계산하지 않도록 배열 같은 곳에 저장해두고, 필요할 때 꺼내서 쓰는 것입니다.
이를 메모이제이션(memoization) 이라고 부릅니다. 작은부분들에 대한 계산값을 메모해두는 것이죠.
대부분의 DP문제들은 점화식을 알면 풀 수 있습니다.
피보나치 수열의 경우 fibonacci(n) = fibonacci(n-1)+fibonacci(n-2) 가 점화식입니다.
n번째를 구하기 위해서 n-1,n-2번째를 알아야하므로 작은부분의 답을 알면 큰부분의 답을 구할 수 있죠.
#include <iostream>
using namespace std;
int main(){
int n; // 범위 0<=n<=40
cin>>n;
int *fibonacci = new int[n+1]; //메모할 배열
fibonacci[0] = 0;
fibonacci[1] = 1;
for(int i = 2;i<=n;i++){
fibonacci[i] = fibonacci[i-1]+fibonacci[i-2]; //fibonacci점화식
}
cout<<fibonacci[n]<<endl;
}
저는 구할만큼의 배열을 동적으로 할당한후, n-1,n-2번째 배열값이 없는 0,1의 경우 초기값을 주고
2부터 구하고 싶은 배열까지 for문을 통해 값을 메모 했습니다.
위처럼 DP알고리즘을 이용할 때는 작은부분의 답을을 이용해 큰부분의 답이 구해지는 경우에 해당하며,
구한 값을 미리 메모해두어 기억하고 다시 사용한다는 것을 알아두시면 되겠습니다!
문제들이 대부분 규칙을 알고 점화식을 세우면 풀 수 있기 때문에 여러DP문제를 풀어보시면서 감을 잡으시면 되겠습니다!
다이나믹 프로그래밍 문제모음(백준) https://www.acmicpc.net/problem/tag/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D
'🕹️ 알고리즘' 카테고리의 다른 글
[알고리즘]깊이우선탐색(DFS),너비우선탐색(BFS) (0) | 2020.12.29 |
---|---|
[알고리즘]완전탐색(Brute-force) (0) | 2020.12.27 |
[알고리즘]삽입정렬(Insertion Sort) (0) | 2020.08.28 |
[알고리즘]선택정렬(Selection Sort) (0) | 2020.08.26 |
[알고리즘]버블 정렬(Bubble Sort) (0) | 2020.08.25 |