1. 다이나믹 프로그래밍이란?
2. 다이나믹 프로그래밍의 속성
3. 다이나믹 문제 푸는 방법
4. 다이나믹 문제 풀이 전략
5. 다이나믹 프로그래밍 문제
1. 다이나믹 프로그래밍이란?
다이나믹 프로그래밍
:Dynamic Programming
큰 문제를 작은 문제를 나눠서 푸는 알고리즘
1940년대 수학자인 Richard Bellman은 'Dynamic Programming'이란 용어를 사용했다.
그는 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다.
큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 계획법(Programming)인것이다.
2. 다이나믹 프로그래밍의 속성
알고리즘 측면에서 다이나믹 프로그래밍은 두 가지 속성이 있다.
1. 겹치는 부분 문제(Overlapping Subprobelm)
2. 문제의 정답을 작은 문제의 정답에서 구할 수 있다.(Optimal Substructure)
두 가지 속성에 대한 세부 내용은 아래와 같다.
1. 겹치는 부분 문제(Overlapping Subprobelm)
1.1 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
1.2 문제를 작은 문제로 쪼갤 수 있다.
(큰 문제를 작은 문제로 나눈다, 여기서 크다와 작다는 상대적이다.
예를 들어, 문제를 Top_down과Bottom-up 두 가지 방식으로 나눠서 풀 경우, 큰 문제와 작은 문제라는 개념은 상대적이기 때문이다.)
1번 속성은 피보나치 수를 이용해서 설명하기 좋다.
작은 문제와 큰 문제가 겹치며, 또한 작은 문제가 겹쳐있다.
다이나믹 프로그래밍은 문제를 작은 문제로 나눠서 푸는 것이 중점이다.
ex) 피보나치 수 : 0, 1, 1, 2, 3, 4, 8, 13, 21, 34, ......,
F(n) = F(n-1) + F(n-2)
문제 : N번째 피보나치 수를 구하는 문제
작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
F(n) = F(n-1) + F(n-2)
= F(n-2) + F(n-3) + F(n-3) + F(n-4)
N-2 가 겹치고 N-3 이 겹친다.
고로 작은 문제가 겹치므로 다이나믹 프로그래밍의 성질이 된다.
2. 문제의 정답을 작은 문제의 정답에서 구할 수 있다.(Optimal Substructure)
ex) 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면
대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.
서울 - 대전 - 대구 - 부산
대전 - 대구 - 부산
이를 피보나치에 적용한다면?
문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.
Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.(예를들어 위의 F(n-5)는 모두 동일하다.)
다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.
Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.
따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다.
이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.
메모를 한다고 해서 영어로 Memoization이라고 한다.
int fibonacci(int n){
if(n<=1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
위에서 중복을 제거할 경우.
memo[n] = n번째 피보나치 수
위의 제귀함수에서 메모를 읽는 코드와 메모를 쓰는 코드를 추가하면 된다.
int memo[100];
int fibonacci(int n){
if(n<=1) {
return n;
} else {
if(memo[n] > 0) { //메모가 되어 있는지.
return memo[n];
}
memo[n] = fibonacci(n-1) + fibonacci(n-2);
return memo[n];
}
}
3. 다이나믹 문제 푸는 방법
다이나믹은 구현 방법에 따라 두 가지 방법이 있다.
1. Top-down
2. Bottom-up
1. 탑다운[Top_down]
Top_down은 재귀함수를 호출해서 구현할 수 있다.
이 방법은 시간 복잡도를 계산하기 까다롭다.
시간복잡도 = memo에 몇 개의 배열이 채워질 것인지(채워야 할 칸의 개수) * 한 칸을 채우는 복잡도
= N * O(1) -> O(N)
1. 문제를 풀어야 한다.
fibonacci(n)
1.1 문제를 작은 문제로 나눈다.
fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다.
1.2 작은 문제를 푼다.
fibonacci(n-1)가 fibonacci(n-2)를 호출해 문제를 푼다.
1.3 작은 문제를 풀었으니, 이제 문제를 푼다.
fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 문제를 푼다.
2. Bottom-up
Bottom-up은 for문 형태로 구현이 된다.
2.1 문제를 크기가 작은 문제부터 차례대로 푼다.
2.2 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
2.3 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
2.4 그러다 보면, 언젠간 풀어야 하는 문제를 풀 수 있다.
int d[100];
int fibonacci(int n) {
d[0] = 0;
d[1] = 1;
for(int i=2; i<=n; i++) { //제일 작은 문제에서 제일 큰 문제까지.
d[i] = d[i-1] + d[i-2];
}
return d[n];
}
4. 다이나믹 문제 풀이 전략
문제에서 구하려고 하는 답을 문장으로 나타낸다.
ex)피보나치 수를 구하는 문제=N번째 피보나치 수
이제 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.
문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 하거나,
점화식을 만들어서 테이블을 키워나가는 형식을 생각한다.
다이나믹은 문제를 많이 풀면서 감을 잡는 게 중요하다.
'Algorithm > Basic' 카테고리의 다른 글
수학 (0) | 2021.01.08 |
---|---|
다이나믹 프로그래밍[Dynamic Programming] 연습하기 좋은 문제 및 풀이 (0) | 2020.12.28 |
자료구조 : 문자열 (0) | 2019.06.06 |
자료구조 : 덱(deque) (0) | 2019.06.06 |
자료구조 : 큐(queue) (0) | 2019.06.06 |