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
|
//code 8.14 원주율 외우기 문제
const int INF = 987654321;
string N;
//N[a..b] 구간의 난이도를 반환한다.
int classify(int a, int b) {
//숫자 조각을 가져온다.
string M = N.substr(a, b - a + 1);
//첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
if (M == string(M.size(), M[0])) return 1;
//등차수열인지 검사한다.
bool progressive = true;
for (int i = 0; i < M.size() - 1; ++i)
if (M[i + 1] - M[i] != M[1] - M[0])
progressive = false;
//등차수열이고 공차가 1혹은 -1이면 난이도는 2
if (progressive && abs(M[1] - M[0]) == 1)
return 2;
//두 수가 번갈아 등장하는지 확인한다.
bool alternating = true;
for (int i = 0; i < M.size(); ++i)
if (M[i] != M[i % 2])
alternating = false;
if (alternating) return 4;
if (progressive) return 5;
return 10;
}
int cache[10002];
//수열 N[begin..]를 외우는 방법 중 난이도의 최소 합을 출력한다.
int memorize(int begin) {
//기저 사례 : 수열의 끝에 도달했을 경우
if (begin == N.size()) return 0;
//메모이 제이션
int& ret = cache[begin];
if (ret != -1) return ret;
ret = INF;
for (int L = 3; L <= 5; ++L)
if (begin + L <= N.size())
ret = min(ret, memorize(begin + L) + classify(begin, begin + L - 1));
return ret;
}
| cs |
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include <iostream>
#include <algorithm>
using namespace std;
////code 8.13
//입력이 32비트 부호있는 정수의 모든 값을 가질 수 있으므로
//인위적인 최소치는 64비트여야 한다.
const long long NEGINF = numeric_limits<long long>::min();
int n, m, A[100], B[100];
int cache[101][101];
//min(A[indexA],B[indexB],max(A[indexA],B[indexB])로 시작하는 합친 증가 부분 수열의 최대 길이를 반환한다.
//단, indexA == indexB == -1 혹은 A[indexA] != B[indexB]라고 가정한다.
int jlis(int indexA, int indexB) {
//메모이제이션
int& ret = cache[indexA + 1][indexB + 1];
if (ret != -1) return ret;
//A[indexA],B[indexB]가 이미 존재하므로 2개는 항상 있다.
ret = 2;
long long a = (indexA == -1 ? NEGINF : A[indexA]);
long long b = (indexB == -1 ? NEGINF : B[indexB]);
long long maxElement = max(a, b);
//다음원소를 찾는다.
for (int nextA = indexA + 1; nextA < n; ++nextA)
if (maxElement < A[nextA])
ret = max(ret, jlis(nextA, indexB) + 1);
for (int nextB = indexB + 1; nextB < n; ++nextB)
if (maxElement < A[nextB])
ret = max(ret, jlis(indexA, nextB) + 1);
return ret;
}
////code 8.12
//int n;
//int cache[101], S[100];
////S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
//int lis3(int start) {
// int& ret = cache[start + 1];
// if (ret != -1) return ret;
// // 항상 S[start]는 있기 때문에 길이는 최하 1
// ret = 1;
// for (int next = start + 1; next < n; ++next) {
// if (start == -1 || S[start] < S[next])
// ret = max(ret, lis3(next) + 1);
// }
// return ret;
//}
////code 8.11
//int n;
//int cache[100], S[100];
////S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
//int lis2(int start) {
// int& ret = cache[start];
// if (ret != -1) return ret;
// // 항상 S[start]는 있기 때문에 길이는 최하 1
// ret = 1;
// for (int next = start + 1; next < n; ++next) {
// if (S[start] < S[next])
// ret = max(ret, lis2(next) + 1);
// }
// return ret;
//}
//
//int maxLen = 0;
//for (int begin = 0; begin < n; ++begin) {
// maxLen = max(maxLen, lis2(begin));
//}
////code 8.10
//int lis(const vector<int>& A) {
// //기저
// if (A.empty()) return 0;
// int ret = 0;
// for (int i = 0; i < A.size(); ++i) {
// vector<int> B;
// for (int j = i + 1; j < A.size(); ++j) {
// if (A[i] < A[j])
// B.push_back(A[j]);
// }
// ret = max(ret, 1 + lis(B));
// }
// return ret;
//}
////code 8.9
//
//int n/*줄*/, triangle[100][100];
//int cache2[100][100];
////(y,x) 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환한다.
//int path2(int y, int x) {
// //기저
// if (y == n - 1) return triangle[y][x];
// //메모이제이션
// int& ret = cache2[y][x];
// if (ret != -1)
// return ret;
// return ret = max(path2(y + 1, x), path2(y + 1, x + 1)) + triangle[y][x];
//}
////code 8.8
//
//int n/*줄*/, triangle[100][100];
//int cache[100][100][MAX_NUMBER * 100 + 1];
////(y,x) 위치까지 내려오기 전에 만난 숫자들의 합이 sum일때
////맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로를 반환한다.
//int path1(int y, int x, int sum) {
// //기저: 맨 아래 줄까지 도달했을 경우
// if (y == n - 1) return sum + triangle[y][x];
// //메모이제이션
// int& ret = cache[y][x][sum];
// if (ret != -1) return ret;
// sum += triangle[y][x];
// return ret = max(path1(y + 1, x + 1, sum), path1(y + 1, x, sum));
//}
| cs |
종만북 스터디 코드 22-02-2019
![종만북 스터디 코드 22-02-2019]()
Reviewed by Lifer
on
2/22/2019
Rating:
댓글 없음: