풀 수 있을 것 같지만, 못 풀 것 같기도 한 알고리즘.. dp..
그만큼 제대로 된 이해를 못 하고 있다는 거겠지..?
이번 기회에 확실하게 짚고 넘어가자. 다이나믹 프로그래밍 정리 시작!
-
* 다이나믹 프로그래밍 (DP): 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
(큰 문제를 작은 문제로 나눠서 푸는 알고리즘은 2가지가 있는데 하나가 DP, 하나는 분할 정복 알고리즘(D&C)이다. DP는 나눈 문제들이 중복이 가능하지만, D&C는 중복이 될 수 없다는 차이가 있다.)
- 두 가지 속성을 만족해야 DP를 사용할 수 있다.
1. Overlapping Subproblem : 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야 하고, 문제를 작은 문제로 쪼갤 수 있어야 한다.
2. Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 한다.
- 메모제이션: 위에서 말한 것처럼 DP는 나눈 문제들이 중복이 가능해서 이미 했던 계산을 또 하는 경우가 생긴다. 따라서 이미 구한 정답을 메모 해놓고 활용하는 것이 중요하다.
- 구현 방식으로는 Top-down (재귀 함수), Bottom-up (반복문) 방식이 있다. 시간 차이는 문제에 따라 다르므로 어느 것이 항상 더 빠르다고 할 수 없다. 일단은 DP 자체에 익숙해지자.
- 구하려는 답을 문장으로 -> 변수의 개수만큼 메모하는 배열 생성 -> 작은 문제로 나눠서 해결 : 이렇게 풀면 된다.
간단하게 연습 해보자.
* 1로 만들기 (mid) : 잘 풀릴 거라고 생각했는데 막상 하니까 잘 안 됐다. 설명을 듣고 풀 수 있었다.
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
using namespace std;
int dp[1000001];
// bottom - up
int go(int n)
{
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 2 == 0) {
int t = dp[i / 2] + 1;
if (dp[i] > t) dp[i] = t;
}
if (i % 3 == 0) {
int t = dp[i / 3] + 1;
if (dp[i] > t) dp[i] = t;
}
}
return dp[n];
}
/* top - down
int go(int n)
{
if (n == 1) return 0;
if (dp[n] > 0) return dp[n];
dp[n] = go(n - 1) + 1;
if (n % 3 == 0) {
int temp = go(n / 3) + 1;
if (dp[n] > temp) dp[n] = temp;
}
if (n % 2 == 0) {
int temp = go(n / 2) + 1;
if (dp[n] > temp) dp[n] = temp;
}
return dp[n];
}
*/
int main()
{
int n;
cin >> n;
cout << go(n) << '\n';
return 0;
}
|
cs |
=> 세 가지 경우를 모두 비교 해보고 가장 작은 값을 넣으면 된다.
* 2 x n 타일링 (low) : 앞의 문제로 감을 잡으니까 쉽게 풀렸다. 맨 뒷부분에 관심을 두면 된다.
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
|
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
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#define DIV 10007
using namespace std;
long long d[1001];
// bottom - up
long long go(int n)
{
d[1] = 1;
d[2] = 2;
for (int i = 3; i <= n; i++)
d[i] = (d[i - 1] + d[i - 2]) % DIV;
return d[n];
}
/* top - down
long long go(int n)
{
if (n == 1) return 1;
if (n == 2) return 2;
if (d[n] > 0) return d[n];
d[n] = (go(n - 1) % DIV + go(n - 2) % DIV) % DIV;
return d[n];
}
*/
int main()
{
int n;
cin >> n;
cout << go(n) << '\n';
return 0;
}
|
cs |
* 2xn 타일링 2 (low) : 앞의 문제에 조건이 하나 추가된 버전이다.
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
|
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
31
32
33
34
35
36
37
38
39
|
#include <iostream>
#define DIV 10007
using namespace std;
long long d[1001];
// bottom-up
long long go(int n)
{
d[1] = 1;
d[2] = 3;
for (int i = 3; i <= n; i++)
d[i] = (d[i - 1] % DIV + 2 * d[i - 2] % DIV) % DIV;
return d[n];
}
/* top-down (시간 초과)
long long go(int n)
{
if (n == 1) return 1;
if (n == 2) return 3;
if (d[n] > 0) return d[n];
return (go(n - 1) % DIV + 2 * go(n - 2) % DIV) % DIV;
}
*/
int main()
{
int n;
cin >> n;
cout << go(n) << '\n';
return 0;
}
|
cs |
=> 얘는 top-down을 쓰면 시간초과가 뜬다. 뭔가 재귀는 코드 상으로 보면 멋지긴 한데.. 불확실한 느낌이 좀 있다. 무조건 top-down을 써야 이득인 상황이 아니면 bottom-up을 사용해야겠다..
* 1, 2, 3 더하기 (low): 위의 문제들과 비슷한 원리로 접근하면 풀 수 있다.
9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는
www.acmicpc.net
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
using namespace std;
int d[12];
// bottom-up
int go(int n)
{
d[1] = 1;
d[2] = 2;
d[3] = 4;
for (int i = 4; i <= n; i++)
d[i] = d[i - 1] + d[i - 2] + d[i - 3];
return d[n];
}
/* top-down
int go(int n)
{
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
if (d[n] > 0) return d[n];
return go(n - 1) + go(n - 2) + go(n-3);
}
*/
int main()
{
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << go(n) << '\n';
}
return 0;
}
|
cs |
-
아직까지는 기본적인 문제 위주다.
DP는 특히 문제를 푸는 감각이 중요하다고 들었는데, 이후의 강의도 그렇게 구성이 되어 있는 것 같다.
차근차근 따라가 봐야겠다.
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제2) (0) | 2020.07.09 |
|---|---|
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제1) (0) | 2020.07.09 |
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 수학1 (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 자료구조1 (연습) (0) | 2020.07.06 |
