출저 - > 유튜브 강의 https://www.youtube.com/watch?v=0o2hF-To_6Q 를 보면서 정리
[ 다이나믹 프로그래밍 ]
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
- 두가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.
1. Overlapping Subproblem (겹치는 부분문제)
2. Optimal Substructure (최적 부분구조)
ex - 피보나치 수
1 2 3 4 5 6 7 8 9 10 11 | int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } | cs |
아래와 같이 중복되는 문제 발생
ex - 중복을 제거한 메모된 피보나치 수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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]; } } | cs |
다이나믹을 푸는 두 가지 방법이 있다.
1. Top-down
2. Bottom-up
아래는 Bottom-up을 통해 피보나치를 해결한 것이다.
1 2 3 4 5 6 7 8 9 10 11 | int d[100]; int fibonacci(int n) { d[0] = 1; d[1] = 1; for (int i = 2; i <= n; i++) { d[i] = d[i - 1] + d[i - 2]; } return d[n]; } | cs |
10->5->4->2->1 보다
10->9->3->1 이 더 빠르다.
위 '1로 만들기' 문제를 Top-down 방식으로 풀게 되면..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | int go(int n) { if (n == 1) return 0; // memoization if (d[n] > 0) return d[n]; // N -> N-1 d[n] = go(n - 1) + 1; // N -> N/2 if (n % 2 == 0) { int temp = go(n / 2) + 1; if (d[n] > temp) d[n] = temp; } // N -> N/3 if (n % 3 == 0) { int temp = go(n / 3) + 1; if (d[n] > temp) d[n] = temp; } return d[n]; } |
그리고, Bottom-up 방식으로 풀게 되면...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int main() { d[1] = 0; for (int i = 2; i <= n; i++) { // N -> N-1 d[i] = d[i - 1] + 1; // N -> N/2 if (i % 2 == 0 && d[i] > d[i / 2] + 1) { d[i] = d[i / 2] + 1; } // N -> N/3 if (i % 3 == 0 && d[i] > d[i / 3] + 1) { d[i] = d[i / 3] + 1; } } } | cs |
타일링 https://www.acmicpc.net/problem/1793
2*n 타일링 https://www.acmicpc.net/problem/11726
2*n 타일링2 https://www.acmicpc.net/problem/11727
https://www.acmicpc.net/problem/9095
1시간 13분까지 들었당.
내일은 붕어빵 판매하기부터 들어야지.
'NOTE > Algorithm' 카테고리의 다른 글
| [알고리즘] 에러의 종류 (펌) (0) | 2018.04.01 |
|---|---|
| [알고리즘문제] DFS와 BFS (0) | 2018.04.01 |
| [알고리즘문제] 백준_음계 (0) | 2018.04.01 |
| [알고리즘문제] 백준_OX퀴즈 (0) | 2018.04.01 |
| [Algorithm] A* 알고리즘 (0) | 2016.11.23 |