[자료구조] TRIE 예제 코드

Programming/Algorithm 2017. 12. 6. 16:23 Posted by gaeddong2
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
/*예제코드 (1)*/
 
#include <stdio.h>
 
 
 
struct Node {
 
    int c[26];
 
    int cnt;
 
};
 
static int n;
 
static Node node_list[1000000];
 
static int root;
 
 
 
int makeNode() {
 
    for (int i = 0; i < 26; i++)
 
        node_list[n].c[i] = 0;
 
    node_list[n].cnt = 0;
 
 
 
    return n++;
 
}
 
 
 
void init(void) {
 
    n = 1;
 
    root = makeNode();
 
}
 
 
 
void insert(int buffer_size, char *buf) {
 
    int me = root;
 
    int i;
 
    for (i = 0; i < buffer_size; i++) {
 
        int k = buf[i] - 'a';
 
        if (node_list[me].c[k] == 0) {
 
            node_list[me].c[k] = makeNode();
 
        }
 
        node_list[me].cnt++;
 
        me = node_list[me].c[k];
 
    }
 
    node_list[me].cnt++;
 
}
 
 
 
int query(int buffer_size, char *buf) {
 
    int me = root;
 
    int i;
 
    for (i = 0; i < buffer_size; i++) {
 
        int k = buf[i] - 'a';
 
        if (node_list[me].c[k] == 0) {
 
            return 0;
 
        }
 
        me = node_list[me].c[k];
 
    }
 
    return node_list[me].cnt;
 
}
 
int main(void)
 
{
 
    init();
 
    insert(4, "abcd");
 
    insert(4, "abce");
 
    insert(4, "abcf");
 
    insert(4, "abcg");
 
    insert(4, "abch");
 
    insert(4, "ffff");
 
    printf("%d", query(4, "ffff"));
 
    return 0;
 
}
 
 
 
 
 
/*예제코드 (2)*/
 
struct Trie
 
{
 
    int cnt;
 
    Trie* next[26];
 
};
 
 
 
Trie *trie;
 
 
 
void init(void)
 
{
 
    trie = new Trie();
 
}
 
 
 
void insert(int buffer_size, char *buf)
 
{
 
    Trie *temp = trie;
 
    for (int i = 0; i < buffer_size; ++i)
 
    {
 
        Trie *newNode = new Trie();
 
        int now = buf[i] - 'a';
 
        if (temp->next[now] == '\0')
 
        {
 
            temp->next[now] = newNode;
 
        }
 
        temp = temp->next[now];
 
        temp->cnt++;
 
    }
 
}
 
 
 
int query(int buffer_size, char *buf)
 
{
 
    Trie *temp = trie;
 
    for (int i = 0; i < buffer_size; i++)
 
    {
 
        int now = buf[i] - 'a';
 
        if (temp->next[now] == '\0')return 0;
 
        temp = temp->next[now];
 
    }
 
    return temp->cnt;
 
}
 
 
 
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

DFS을 이용한 순열구하기  (0) 2018.04.09
순열 및 조합 참고 링크  (0) 2018.04.02
원하는 개수의 순열 구하기  (0) 2016.04.01
긴 자리 덧셈 뺄셈 계산하는 코드  (0) 2016.03.24
알고리즘 학습 사이트  (0) 2016.03.24

원하는 개수의 순열 구하기

Programming/Algorithm 2016. 4. 1. 14:49 Posted by gaeddong2
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
#include <stdio.h>
 
 
 
int arr[5] = { 1, 2, 3 ,4,5};
 
int tmp[5];
 
int Visited[5];
 
void print(int a[])
 
{
 
    int i;
 
    for (i = 0; i < 5; i++)
 
    {
 
        printf("%d ", arr[tmp[i]]);
 
    }
 
    printf("\n");
 
}
 
void perm(int index[], int pos, int len, int depth)
 
{
 
    int i;
 
    if (pos == depth)
 
    {
 
        print(index);
 
        return;
 
    }
 
    for (i = 0; i < len; i++)
 
    {
 
        if (Visited[i] == 0)
 
        {
 
            Visited[i] = 1;
 
            index[pos] = i;
 
            perm(index, pos + 1, len, depth);
 
            Visited[i] = 0;
 
        }
 
    }
 
}
 
int main(void)
 
{
 
    perm(tmp, 0, 5, 5);
 
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

순열 및 조합 참고 링크  (0) 2018.04.02
[자료구조] TRIE 예제 코드  (0) 2017.12.06
긴 자리 덧셈 뺄셈 계산하는 코드  (0) 2016.03.24
알고리즘 학습 사이트  (0) 2016.03.24
길찾기 알고리즘(0 에서 99로 갈 수 있는지 확인)  (0) 2016.03.11

긴 자리 덧셈 뺄셈 계산하는 코드

Programming/Algorithm 2016. 3. 24. 15:21 Posted by gaeddong2

참조 : http://sirini.net/grboard2/blog/view/741

/* 이 소스코드는 기존 C 언어에서 지원하지 않는
무한자리수 산수 연산을 예시한다. 기본 데이터타입의 범위를 초과한
데이터의 덧셈과 뺄셈을 처리한다. */


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
#define LIMIT 32 /* 일단 여기서는 편의상 32자리 수로 제한한다. */
#define NUM ( ((LIMIT-1) / 4) + 1 ) /* 배열 크기다. short 타입의 배열을 쓴다. */
 
void iAdd(short*, short*, short*); /* 덧셈 */
void iSub(short*, short*, short*); /* 뺄셈 */
void iResult(short*); /* 결과 출력용 */
 
int main(int args)
{
    // 임의로 큰 수를 4자리로 short 배열에 담아두었다.
    // 실제 활용시에는 이 부분도 자동으로 되겠금 처리하는 게 좋다.
    static short a[NUM+2] = {1522,7849,2969,5432,1562,5092,8504,9562},
            b[NUM+2] = { 592,1949,6040,2947,6029,1156,5892,6782},
            c[NUM+2];
    
    printf("연산대상 A: 1522,7849,2969,5432,1562,5092,8504,9562￦n");
    printf("연산대상 B:  592,1949,6040,2947,6029,1156,5892,6782￦n");
    printf("---------------------------------------------------￦n");
    
    iAdd(a, b, c);
    printf("덧셈결과 +: ");
    iResult(c);
    
    iSub(a, b, c);
    printf("뺄셈결과 -: ");
    iResult(c);
    
    return 0;
}
 
// 긴 자리 덧셈하기
void iAdd(short a[], short b[], short c[])
{
    short i, cy=0;
    
    // 배열의 뒷자리부터 (그러니까 작은 단위수부터) 한 인덱스씩 계산한다.
    // 한 블럭의 덧셈결과가 10000 을 넘게 되면 자리올림수 처리를 해준다. (cy)
    for (i=NUM-1; i>=0; i--) {
        c[i] = a[i] + b[i] + cy;
        
        // 4자리수끼리 덧셈을 했는데도 10000 을 못넘겼으면 자리올림수는 없다!
        if(c[i] < 10000)
            cy = 0;
        else {
            c[i] = c[i] - 10000;
            cy = 1; // 덧셈해서 10000 을 넘겼다면 자리올림수를 만든다.
            // 위에서 만들어진 자리올림수는 그대로 다음 루프문에서 반영된다.
        }
    }
}
 
// 긴 자리수 뺄셈하기
void iSub(short a[], short b[], short c[])
{
    short i, br=0;
    
    // 역시 배열의 뒷자리 블럭부터 4자리씩 끊어서 계산한다.
    for (i=NUM-1; i>=0; i--) {
        c[i] = a[i] - b[i] - br;
        
        // 4자리수 뺄셈해서 결과가 0 이거나 혹은 0보다 크면 자리내림수는 없다!
        if (c[i] >= 0)
            br = 0;
        else {
            c[i] = c[i] + 10000; // 0보다 작게 되었다면 10000 을 빌리고
            br = 1; // 대신 그 윗자리수에서 1을 뺀다. 등가교환법칙
        }
    }
}
 
// 출력용
void iResult(short c[])
{
    short i;
    
    // 저장된 배열을 역시 4자리씩 끊어서 보여준다.
    for (i=0; i<NUM; i++)
        printf("%04d ", c[i]);
    printf("￦n");
}
cs


저작자표시

'Programming > Algorithm' 카테고리의 다른 글

[자료구조] TRIE 예제 코드  (0) 2017.12.06
원하는 개수의 순열 구하기  (0) 2016.04.01
알고리즘 학습 사이트  (0) 2016.03.24
길찾기 알고리즘(0 에서 99로 갈 수 있는지 확인)  (0) 2016.03.11
멱집합(부분집합) 응용, 조건에 따라 불필요한 부분집합 제거  (0) 2016.03.10
 

티스토리툴바