Strong Root

Apriori 알고리즘

뿌리튼튼 CS/Data Mining2015. 4. 10. 14:27

난이도 ★★★★★ (너무 어렵다)


요구사항

● 실행파일 이름 : apriori.exe


● 실행프로그램 인자 : minimum support, input file name, output file name




● 입력파일 형식




● 출력파일 형식


● 기타 주의사항

1. 실행시 인자로 넘겨주는 Min Support값과 출력시 Support값은 %값이다.

2. 출력파일에서의 행별 정렬 순서는 중요하지 않다.


● 결과 테스트용 입력 파일

input.txt


● 결과 테스트용 출력 파일

1. Min Support = 10%

output_10.txt


2. Min Support = 9%

output_9.txt


3. Min Support = 6%

output_6.txt


4. Min Support = 2% (굉장히 오래걸림. 1시간 이상)

output_2.txt


● 소스 코드 (답은 맞지만 느립니다. 최적의 코드가 결코 아닙니다)

1. 직접 다운

apriori.cpp


2. 소스 보기

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
#include <stdio.h>
#include <stdlib.h>
 
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
 
#include <set>
#include <algorithm>
 
#include <iomanip>
 
#define DEBUG_MODE true
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    set<int> itemset;
    int sup;
} Itemset;
 
void makeC(vector<Itemset> *pC, vector<Itemset> *pLi) {
    pC->clear();
 
    // self-joining L
    for (int i = 0; i < pLi->size() - 1; i++) {
        for (int j = i + 1; j < pLi->size(); j++) {
            // get L(i) - L(j)
            set<int> i_diff_j;
            set_difference(pLi->at(i).itemset.begin(), pLi->at(i).itemset.end(),
                pLi->at(j).itemset.begin(), pLi->at(j).itemset.end(),
                inserter(i_diff_j, i_diff_j.end()));
 
            // if could
            if (i_diff_j.size() == 1) {
                // generate a candidate
                set<int> candidate;
 
                candidate.insert(pLi->at(j).itemset.begin(), pLi->at(j).itemset.end());
                candidate.insert(i_diff_j.begin(), i_diff_j.end());
 
                // redundancy check
                bool found = false;
                for each (Itemset c in *pC) {
                    set<int> result;
                    set_difference(c.itemset.begin(), c.itemset.end(), candidate.begin(), candidate.end(), inserter(result, result.end()));
                    if (result.empty()) {
                        found = true;
                        break;
                    }
                }
 
                // if not found, push
                if (!found) {
                    Itemset item;
 
                    item.itemset = candidate;
                    item.sup = 0;
 
                    pC->push_back(item);
                }
            }
        }
    }
 
    // if don't need to be pruned, return
    if ((pC->size() < 1) || (pC->at(0).itemset.size() < 3)) {
        return;
    }
 
    // pruning
    int i = 0;
    while (true) {
        if (i >= pC->size()) {
            break;
        }
 
        for (int j = 0; j < pC->at(i).itemset.size(); j++) {
            // get subSet which excludes jth number
            set<int> subSet;
 
            set<int>::iterator it = pC->at(i).itemset.begin();
            if (j == 0) {    // first
                std::advance(it, 1);
                subSet.insert(it, pC->at(i).itemset.end());
            }
            else if (j == pC->at(i).itemset.size() - 1) {    // last
                std::advance(it, j);
                subSet.insert(pC->at(i).itemset.begin(), it);
            }
            else {    // else
                std::advance(it, j);
                subSet.insert(pC->at(i).itemset.begin(), it);
 
                std::advance(it, 1);
                subSet.insert(it, pC->at(i).itemset.end());
            }
 
            // check
            bool found = false;
            for each (Itemset l in *pLi) {
                set<int> result;
                set_difference(subSet.begin(), subSet.end(), l.itemset.begin(), l.itemset.end(), inserter(result, result.end()));
                if (result.empty()) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                pC->erase(pC->begin() + i);
                i--;
                break;
            }
        }
 
        i++;
    }
}
 
void makeL(vector<vector<Itemset>> *pL, vector<Itemset> *pC, int minSupport) {
    vector<Itemset> Li;
 
    for each (Itemset c in *pC) {
        if (c.sup >= minSupport) {
            Itemset item;
 
            item.itemset = c.itemset;    // could generate error
            item.sup = c.sup;
 
            Li.push_back(item);
        }
    }
 
    pL->push_back(Li);
 
    if (DEBUG_MODE) {
        printf("\n************************\n");
        int i = pL->size() - 1;
        printf("L[%d] (size = %d, minSup = %d)\n", i, pL->at(i).size(), minSupport);
        for each (Itemset l in pL->at(i)) {
            printf("{ ");
            for each (int num in l.itemset) {
                printf("%d ", num);
            }
            printf(" }, %d\t", l.sup);
        }
        printf("\n*************************\n");
    }
}
 
set<set<int>> findSubsets(set<int> A) {
    if (A.empty()) {
        set<set<int>> ret;
        return ret;
    }
 
    set<int> tmp;
    set<int>::iterator it = A.begin();
    std::advance(it, 1);
    tmp.insert(it, A.end());
 
    set<set<int>> B = findSubsets(tmp);
 
    set<set<int>> C;
 
    int A0 = *A.begin();
    for each (set<int> D in B) {
        set<int> temp;
        temp.insert(A0);
        temp.insert(D.begin(), D.end());
        C.insert(temp);
 
        set<int> temp2;
        temp2.insert(A0);
        C.insert(temp2);
    }
    if (B.empty()) {
        set<int> temp;
 
        temp.insert(A0);
 
        C.insert(temp);
    }
 
    B.insert(C.begin(), C.end());
 
    return B;
}
 
int getSupport(set<int> *itemset, vector<vector<Itemset>> *pL) {
    for each (Itemset l in pL->at(itemset->size() - 1)) {
        set<int> result;
        set_difference(l.itemset.begin(), l.itemset.end(), itemset->begin(), itemset->end(), inserter(result, result.end()));
        if (result.empty()) {
            return l.sup;
        }
    }
 
    return -1;
}
 
int main(int argc, char** argv) {
    if (argc != 4) {
        cout << "Error Code: 001" << "\n" << "argc should be 4" << endl;
        return 0;
    }
 
    int relativeSupport = atoi(argv[1]);
    char* inputFileName = argv[2];
    char* outputFileName = argv[3];
 
    if (DEBUG_MODE) {
        printf("%d %s %s\n", relativeSupport, argv[2], argv[3]);
    }
 
    int sizeOfTransactions = 0;
 
    // scan to increment the count of all candidates in C(1)
    vector<vector<Itemset>> L;    // L(i) : frequent itemset of size i
    vector<Itemset> C;    // C(i) : candidate itemset of size i
    ifstream inputFile(inputFileName);
    if (inputFile.is_open()) {
        string line;
        while (getline(inputFile, line)) {
            sizeOfTransactions++;
 
            // get transaction
            set<int> transaction;
            stringstream ss(line);
            int num;
            while (ss >> num) {
                transaction.insert(num);
 
                // find num in C
                int target = -1;
                for (int i = 0; i < C.size(); i++) {
                    if (C[i].itemset.find(num) != C[i].itemset.end()) {
                        target = i;
                        break;
                    }
                }
 
                // not found
                if (target == -1) {
                    Itemset item;
 
                    item.itemset.insert(num);
                    item.sup = 0;
 
                    C.push_back(item);
                }
 
                // found
                else {
                    C[target].sup++;
                }
            }
 
            // get C's sup
            for each (Itemset c in C) {
                set<int> result;
                set_difference(c.itemset.begin(), c.itemset.end(), transaction.begin(), transaction.end(), inserter(result, result.end()));
                if (result.empty()) {
                    c.sup++;
                }
            }
        }
        inputFile.close();
    }
    else {
        cout << "Error Code: 002" << "\n" << "Cannot open input file. (name: " << inputFileName << ")" << endl;
        return 0;
    }
 
    // get minSupport
    int minSupport = ceil(((double)sizeOfTransactions / 100) * relativeSupport);
 
    // get L(1)
    makeL(&L, &C, minSupport);
 
    // get C(i) & L(i) where i > 1
    int i = 0;
    while (true) {
        // get C(i+1)
        makeC(&C, &L[i]);
 
        // if cannot generate C(i+1), break
        if (C.empty()) {
            break;
        }
 
        // scan to increment the count of all candidates in C
        ifstream inputFile(inputFileName);
        if (inputFile.is_open()) {
            string line;
            while (getline(inputFile, line)) {
                // get transaction
                set<int> transaction;
                stringstream ss(line);
                int num;
                while (ss >> num) {
                    transaction.insert(num);
                }
 
                // get C's sup
                for (int j = 0; j < C.size(); j++) {
                    set<int> result;
                    set_difference(C[j].itemset.begin(), C[j].itemset.end(), transaction.begin(), transaction.end(), inserter(result, result.end()));
                    if (result.empty()) {
                        C[j].sup++;
                    }
                }
            }
            inputFile.close();
        }
        else {
            cout << "Error Code: 003(" << i << ")" << "\n" << "Cannot open input file. (name: " << inputFileName << ")" << endl;
            return 0;
        }
 
        // get L(i+1)
        makeL(&L, &C, minSupport);
 
        i++;
    }
    
    // output
    ofstream outputFile(outputFileName);
    if (outputFile.is_open()) {
        printf("\n*** output... ***\n");
        outputFile << fixed << setprecision(2);
        for (int i = 1; i < L.size(); i++) {
            for (int j = 0; j < L.at(i).size(); j++) {    // L.at(i) : {itemset}, {itemset}, {itemset}, ...
                // get all sizes of subset
                set<set<int>> subsets = findSubsets(L.at(i).at(j).itemset);    // L.at(i).at(j) : {itemset}
 
                for each (set<int> subset1 in subsets) {
                    set<int> subset2;
                    set_difference(L.at(i).at(j).itemset.begin(), L.at(i).at(j).itemset.end(), subset1.begin(), subset1.end(), inserter(subset2, subset2.end()));
                    if (subset2.empty()) {
                        continue;
                    }
 
                    // print subset1
                    outputFile << "{";
                    int pos = 0;
                    for each (int item in subset1) {
                        outputFile << item;
                        if (pos < subset1.size() - 1) {
                            outputFile << ",";
                        }
                        else {
                            outputFile << "}\t";
                        }
                        pos++;
                    }
 
                    // print subset2
                    outputFile << "{";
                    pos = 0;
                    for each (int item in subset2) {
                        outputFile << item;
                        if (pos < subset2.size() - 1) {
                            outputFile << ",";
                        }
                        else {
                            outputFile << "}\t";
                        }
                        pos++;
                    }
 
                    // print relative support of original set (subset1 + subset2)
                    outputFile << (L.at(i).at(j).sup / (double)sizeOfTransactions) * 100 << "\t";
 
                    // print confidence (original set's support / subset1's support)
                    outputFile << (L.at(i).at(j).sup / (double)getSupport(&subset1, &L)) * 100 << endl;
                }
            }
        }
 
        outputFile.close();
    }
    else {
        cout << "Error Code: 004" << "\n" << "Cannot open output file. (name: " << outputFileName << ")" << endl;
        return 0;
    }
 
    return 0;
}
cs


● 출처 : 2015년 한양대학교 김상욱 교수님의 데이터마이닝 수업 과제


저작자표시 비영리 동일조건

'뿌리튼튼 CS > Data Mining' 카테고리의 다른 글

Decision Tree  (0) 2015.04.23

게임판 덮기(BOARDCOVER) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 28. 11:19

난이도 ★★★★☆


문제를 보시려면 여기를 클릭




힌트

 재귀로 탐색하면 편리하다.

 → ① 왼쪽 위 점을 기준으로 잡고 하면 좋다. 그렇게 되면 가능한 경우가 4가지만 나온다.

 → ② 탐색 중에 덮었으면(cover) 꼭 다시 벗겨줘야(uncover) 한다.



이하는 코드입니다.


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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <stdio.h>
#include <vector>
 
#define WALL 1
#define EMPTY 0
 
#pragma warning(disable:4996)
 
using namespace std;
 
int H, W;
vector<vector<int>> board;
int coverCount;
 
void getCount(int y, int x) {
    // get left-top
    int i, j;
    bool found = false;
    for (i = y; i < H; i++) {
        if (i == y) {
            j = x;
        }
        else {
            j = 0;
        }
        for (; j < W; j++) {
            if (board[i][j] == EMPTY) {
                found = true;
                break;
            }
        }
 
        if (found) {
            break;
        }
    }
 
    // there is no EMPTY → case found
    if (!found) {
        coverCount++;
        return;
    }
 
    // last row → impossible case
    if (i > H - 2) {
        return;
    }
 
    // last column → only 」case could be possible
    if (j > W - 2) {
        // 」
        if ((board[i + 1][j - 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j - 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j - 1]--;
            board[i + 1][j]--;
        }
 
        return;
    }
 
    // neither last row nor last column → all cases could be possible
    else {
        // ㄱ
        if ((board[i][j + 1] == EMPTY) && (board[i + 1][j + 1] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i][j + 1]++;
            board[i + 1][j + 1]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i][j + 1]--;
            board[i + 1][j + 1]--;
        }
 
        // 「
        if ((board[i][j + 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i][j + 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i][j + 1]--;
            board[i + 1][j]--;
        }
 
        // 」
        if ((board[i + 1][j - 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j - 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j - 1]--;
            board[i + 1][j]--;
        }
 
        // ㄴ
        if ((board[i + 1][j] == EMPTY) && (board[i + 1][j + 1] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j]++;
            board[i + 1][j + 1]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j]--;
            board[i + 1][j + 1]--;
        }
    }
}
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    while (C-- > 0) {
        scanf("%d %d\n", &H, &W);
 
        // get board
        for (int i = 0; i < H; i++) {
            vector<int> line;
 
            for (int j = 0; j < W; j++) {
                char c;
                scanf("%c", &c);
 
                if (c == '.') {
                    line.push_back(EMPTY);
                }
                else {
                    line.push_back(WALL);
                }
            }
            board.push_back(line);
 
            // remove '\n'
            getchar();
        }
 
        // solve and print
        coverCount = 0;
        getCount(0, 0);
        printf("%d\n", coverCount);
 
        // reset
        if (C > 0) {
            board.clear();
        }
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

터보모드(TURBOMODE) 정답 코드  (0) 2015.04.10
HOTSUMMER 정답 코드  (0) 2015.04.10
콘서트(CONCERT) 정답 코드  (1) 2015.02.26
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24

콘서트(CONCERT) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 26. 14:18

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

3

1 5 9

5

1 5 9

6

50 1 24

1 2 2 2 4 2 3 2 1 2 3 2 1 2 3 2 3 2 1 2 3 1 2 3 2 5 3 5 3 2 2 5 6 6 7 7 5 8 7 8 7 5 7 5 6 5 6 6 6 4

0

-1

24




힌트

 동적계획법의 전형적인 문제이지만 문제 이해가 좀 어렵다.

 → 이해했다면 동적계획법의 틀(재귀함수 + 캐시)대로 구현하면 된다.



이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#define FAIL -3
#define N_MAX 50
#define VM_MAX 1000
 
#pragma warning(disable:4996)
 
int N, VM;
int board[N_MAX];
int cache[N_MAX + 2][VM_MAX];
 
int getMaxVolume(int VS, int boardIndex) {
    if ((VS < 0) || (VS > VM)) {
        return FAIL;
    }
 
    int& ret = cache[boardIndex][VS];
    if (ret != -1) {
        return ret;
    }
 
    if (boardIndex == N) {
        return ret = VS;
    }
 
    return ret = (MAX(getMaxVolume(VS + board[boardIndex], boardIndex + 1), getMaxVolume(VS - board[boardIndex], boardIndex + 1)));
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get N, VS, VM
        int VS;
        scanf("%d %d %d", &N, &VS, &VM);
 
        // get Vi
        for (int i = 0; i < N; i++) {
            scanf("%d", &board[i]);
        }
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        int maxVolume = getMaxVolume(VS, 0);
        if (maxVolume == FAIL) {
            maxVolume = -1;
        }
        printf("%d\n", maxVolume);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

HOTSUMMER 정답 코드  (0) 2015.04.10
게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23

짝맞추기(MEETING) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 26. 11:01

난이도 ★☆☆☆☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

4

1

0

0

1

-1

-1

4

1 2 3 4

5 3 1 6

3

-1 2 -3

3 -2 1

0

0

5

4




힌트

 정렬만 하면 끝나는 매우 쉬운 문제

 → 'algorithm'의 'sort()' 함수를 사용하면 매우 간단하다.



이하는 코드입니다.


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
#include <stdio.h>
#include <algorithm>
#include <vector>
 
#define ABS(a) (((a) < 0) ? ((a)*(-1)) : (a))
 
#pragma warning(disable:4996)
 
using namespace std;
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get men
        vector<int> men;
        for (int i = 0; i < N; i++) {
            int tmp;
            scanf("%d", &tmp);
            men.push_back(tmp);
        }
 
        // get women
        vector<int> women;
        for (int i = 0; i < N; i++) {
            int tmp;
            scanf("%d", &tmp);
            women.push_back(tmp);
        }
 
        // sort
        sort(men.begin(), men.end());
        sort(women.begin(), women.end());
 
        // get sum
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += ABS(men[i] - women[i]);
        }
 
        // print
        printf("%d\n", sum);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28
콘서트(CONCERT) 정답 코드  (1) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16

달팽이(SNAIL) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 24. 17:08

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

4

1 1

1000 1000

1000 500

1000 600

1.0000000000

1.0000000000

0.0000000000

0.9999980550




힌트

 고등학교 수학문제이지만 계산과정에서 오버플로우가 난다.

 → 분자 분모가 각각 매우 크므로, 따로 계산하지말고 한번에 계산하여 큰값이 존재할 수 없도록 구현한다.



이하는 코드입니다.


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 <stdio.h>
#include <math.h>
 
#pragma warning(disable:4996)
 
// Px = (mCx * 3 ^ x) / 4 ^ m
double getProb(int m, int winCount) {
    double ret = 1.0;
 
    // x번 / x번
    for (int i = m, j = winCount; i > m - winCount; i--, j--) {
        ret = (ret * i * 0.75) / j;
    }
 
    // / (m-x)번
    ret /= pow(4.0, m - winCount);
 
    return ret;
}
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    while (C-- > 0) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        double ret = 0.0;
 
        for (int winCount = n - m; winCount <= m; winCount++) {
            ret += getProb(m, winCount);
        }
 
        printf("%.10f\n", ret);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

콘서트(CONCERT) 정답 코드  (1) 2015.02.26
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
Coin Change(COINS) 정답 코드  (0) 2015.02.23
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12

Coin Change(COINS) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 23. 18:04

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭




힌트

 전형적인 동적계획법 문제

 → 완전 탐색 + 캐시 사용




이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
 
#define C_MAX 100
#define M_MAX 5000
#define MOD_AMOUNT 1000000007
 
#pragma warning(disable:4996)
 
using namespace std;
 
vector<int> coins;
int cache[M_MAX][C_MAX];
 
int getCount(int money, int maxCoinIndex) {
    int& ret = cache[money][maxCoinIndex];
    if (ret != -1) {
        return ret;
    }
 
    // case found
    if (money == 0) {
        return ret = 1;
    }
 
    // if this is a leaf node
    if (maxCoinIndex == 0) {
        if (money % coins[maxCoinIndex] == 0) {
            return ret = 1;
        }
 
        return ret = 0;
    }
 
    // non-leaf node
    ret = 0;
    for (int pSum = 0; pSum <= money; pSum += coins[maxCoinIndex]) {
        ret = (ret + getCount(money - pSum, maxCoinIndex - 1)) % MOD_AMOUNT;
    }
 
    return ret;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get M, C
        int M, C;
        scanf("%d %d", &M, &C);
 
        // get sorted coins
        coins.clear();
        for (int i = 0; i < C; i++) {
            int coin;
            scanf("%d", &coin);
            coins.push_back(coin);
        }
        sort(coins.begin(), coins.end());
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getCount(M, C - 1));
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10

최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 16. 17:23

난이도 ★★★★☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

3

4

10000 -10000

-10000 10000

10000 10000

-10000 -10000

7

2 2

2 4

5 4

5 1

1 1

1 2

2 1

8

7 19

11 15

3 11

3 15

7 11

11 11

3 19

11 19

20000 20000

1 3

8 8




힌트

 정사각형을 만드는 네 점을 잡았다면, 그 네 점은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이런 형태이다.

 → 따라서 같은 값이 하나도 없는 좌표는 탐색할 필요가 없다. 같은 값이 최소 1개 이상 있는 것만 탐색한다.



이하는 코드입니다. (내 생에 최다의 for문 중첩. 무려 7중)


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
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <vector>
#include <algorithm>
 
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int x;
    int y;
}Point;
 
bool myCompareX(const vector<Point> left, const vector<Point> right) {
    return left[0].x < right[0].x;
}
 
bool myCompareY(const Point left, const Point right) {
    return left.y < right.y;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
    
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get points
        vector<vector<Point>> points;
        for (int i = 0; i < N; i++) {
            Point *point = new Point;
 
            scanf("%d %d", &point->x, &point->y);
 
            bool found = false;
            for (int j = 0; j < points.size(); j++) {
                if ((points[j].size() > 0) && (points[j][0].x == point->x)) {
                    points[j].push_back(*point);
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                vector<Point> *arr = new vector<Point>;
                arr->push_back(*point);
                points.push_back(*arr);
            }
        }
 
        // trim
        for (int i = 0; i < points.size(); i++) {
            if (points[i].size() < 2) {
                points.erase(points.begin() + i);
            }
        }
 
        // sort
        for (int i = 0; i < points.size(); i++) {
            sort(points[i].begin(), points[i].end(), myCompareY);
        }
        sort(points.begin(), points.end(), myCompareX);
 
        /* find min, max */
        int minLength = 20001, maxLength = 0;
 
        for (int i = 0; i < points.size() - 1; i++) {
            // get x
            for (int j = 0; j < points[i].size() - 1; j++) {
                // (x, y1)
                int y1 = points[i][j].y;
                for (int k = j + 1; k < points[i].size(); k++) {
                    // (x, y2)
                    int y2 = points[i][k].y;
                    int length = y2 - y1;
                    int nextX = points[i][0].x + length;
 
                    // find nextX
                    for (int l = i + 1; l < points.size(); l++) {
                        // nextX found
                        if (points[l][0].x == nextX) {
                            for (int m = 0; m < points[l].size() - 1; m++) {
                                // y1 found
                                if (points[l][m].y == y1) {
                                    for (int n = m + 1; n < points[l].size(); n++) {
                                        // Finally, y2 found
                                        if (points[l][n].y == y2) {
                                            minLength = MIN(minLength, length);
                                            maxLength = MAX(maxLength, length);
                                            break;
                                        }
 
                                        // y2 not found
                                        if (points[l][n].y > y2) {
                                            break;
                                        }
                                    }
                                    break;
                                }
 
                                // y1 not found
                                if (points[l][m].y > y1) {
                                    break;
                                }
                            }
                            break;
                        }
 
                        // nextX not found
                        if (points[l][0].x > nextX) {
                            break;
                        }
                    }
                }
            }
        }
 
        // print
        printf("%d %d\n", minLength, maxLength);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
소풍(PICNIC) 정답 코드  (0) 2015.02.09

[강좌] 초급2 - 버튼 클릭 + 리스너

뿌리튼튼 CS/Android2015. 2. 15. 14:56

<초급1 - 입문 + xml, java 파일 작성법 바로가기>



다음으로 버튼(Button)을 배워보겠습니다.


아래와 같은 화면을 구성해보겠습니다.


[그림2-1] 목표2



먼저 기존의 xml 파일을 아래와 같이 수정합니다.


[그림2-2] activity_my.xml


위와 같이 xml 내용을 입력한 후 미리보기(preview)를 보시면 [그림2-1]와 같은 모습이 보입니다. 이제 뷰는 완성되었습니다.






Java 파일을 아래와 같이 수정합니다.


[그림2-3] MyActivity.java


여기까지 작성한 후 휴대폰을 pc에 연결하고 Run을 시켜봅니다.


어플이 실행되며...는 개뿔 컴파일 에러가 뜹니다. 죄송합니다 ㅎㅎ 코드 설명을 위해 잠깐 멈추었습니다.










[그림2-3]의 빨간 박스 안의 코드를 살펴보겠습니다.







바인딩(Binding)이라고 이름까지 있는 중요한 코드입니다.


xml 상의 뷰를 Java에서 컨트롤할 수 있도록 id값을 통해 말그대로 묶어주는(bind) 역할을 합니다.







위 그림처럼, 바인딩한 Java변수에 점(.)을 찍어보면 굉장히 많은 일들을 할 수 있다는 것을 알 수 있습니다.


xml에서 할 수 있는 일(가로 세로 크기 등)을 Java의 바인딩된 변수를 통해서도 할 수 있습니다.


이 바인딩의 가장 큰 장점은 런타임에서의 동적인 처리를 가능케 한다는 것입니다.







우리는 위 목록 중에서 setOnClickListener(OnClickListener l) 함수를 사용해보겠습니다.


위처럼 타이핑 해보면 괄호 안에 빨간 줄이 그이며 뷰에 등록할 OnClickListner 객체를 쓰라고 합니다.


여기에 OnClickListener 객체를 넣는 방법은 크게 두가지가 있습니다.


① 해당 객체를 그자리에서 new로 생성해주는 방법

② 현재 Activity 클래스 자신이 OnClickListener를 구현(implement)하고 자신(this)을 인자로 넘겨주는 방법


결론부터 말하면 ②가 좋습니다만 ①부터 살펴보겠습니다 ㅎㅎ




<① 해당 객체를 그자리에서 new로 생성해주는 방법>


보통 가장 처음으로 배우는 방법입니다.



위와 같이 코드를 작성하고 'do something' 자리에 하고 싶은 일을 적으면 됩니다.




이 방법은 굉장히 간편합니다. 단, 뷰가 하나일 때만요.


버튼이 두개 이상이라면 어떨까요?



뷰의 개수만큼 OnClickListener 객체를 새로 생성해주고 있습니다.


②를 볼까요?






<② 현재 Activity 클래스 자신이 OnClickListener를 구현(implement)하고 자신(this)을 인자로 넘겨주는 방법>





이해를 위해, 구현(implements)도 상속(extends)과 비슷하다고 보시면 좋습니다.




이렇게 쓰는 순간, MyActivity 자신이 OnClickListener 객체가 되게 됩니다.


즉, MyActivity는 Activity이면서 동시에 OnClickListener인겁니다.




따라서 OnClickListener 객체를 요하는 setOnClickListener() 함수에 자기 자신(this)을 인자로 넘겨주면 되는 것입니다.




보시면, 뷰의 개수가 늘어나도 OnClickListener 객체를 새로 생성하지 않습니다. 메모리가 조금이라도 덜 들어가겠죠.


또한 하나의 onClick()함수만 사용함으로써 코드의 가독성이 훨씬 증가합니다.










다시 본론으로 돌아가서 Java 파일을 완성해보겠습니다.


[그림2-4] MyActivity.java


위와 같이 작성한 후 휴대폰을 pc에 연결하고 Run을 시켜봅니다.


어플이 실행되며 xml 미리보기에서 봤던 것과 같은 화면이 여러분의 휴대폰에서 보일 것입니다.




'첫 버튼'을 클릭했을 때 '첫 토스트'가 뜬다면 성공입니다.










본격적인 안드로이드의 세계로 오신 것을 환영합니다. 


저작자표시 비영리 동일조건

'뿌리튼튼 CS > Android' 카테고리의 다른 글

File to Byte Array (File을 Byte배열로 변환)  (0) 2015.06.12
Android Studio에서 Library 추가시 쓸데없는 Duplicate 오류 대처법  (0) 2015.06.12
[강좌] Android SDK Search - 설치 및 SDK 소스 보기  (0) 2015.01.17
[강좌] 초급1 - 입문 + xml, java 파일 작성법  (0) 2015.01.16
Intent 활용 예시  (0) 2014.11.12

티스토리툴바