SW정리: 알고리즘

레이블이 알고리즘인 게시물을 표시합니다. 모든 게시물 표시

2021년 4월 25일 일요일

TRIE (동적 메모리로 구현)

이번에는 TRIE를 동적 메모리를 이용하여 만들어 보겠습니다.

C++언어를 이용한 방법은 다른곳에서 쉬게 찾을 수 있으므로 여기에서는 C언어를 이용한 구현 코드를 소개합니다.

정적 메모리로 구현한 코드와 큰 차이는 없으며, 다만 메모리 해제하는 부분을 주의 깊게 봐야합니다. C++ 언어에서 클래스의 소멸자를 쓰면 되지만 순수하게 C언어 문법으로 구현한 부분이라 DFS 순회를 통한 메모리 해제를 하도록 구현 하였습니다.

#include <stdio.h>
#include <stdlib.h>

#define ALPHA 26

typedef struct trie_type_s{
	struct trie_type_s *child[ALPHA];
	int done;
}trie_type;

trie_type trie;

void dfs_free(trie_type *node)
{
	int i;
	trie_type *cur_node = node;
	trie_type *child_node;
	for(i=0;i<ALPHA;i++){
		child_node = cur_node->child[i];
		if( child_node != 0 ){
			dfs_free(child_node);
		}
	}
	if( &trie==cur_node ){
		for(i=0;i<ALPHA;i++){
			cur_node->child[i] = 0;
		}
		cur_node->done = 0;
	}else{
		free(cur_node);
	}
}

int init()
{
	dfs_free(&trie);
	return 0;
}

void trie_insert(const char data[])
{
	int i;
	trie_type *cur_node = &trie;
	trie_type *next_node;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node = cur_node->child[data[i]-'a'];
		if( next_node == 0 ){
			// empty child need to add
			trie_type *new_node = (trie_type *)malloc(sizeof(trie_type));
			cur_node->child[data[i]-'a'] = new_node;
			for(int j=0;j<ALPHA;j++){
				new_node->child[j]=0;
			}
			new_node->done = 0;
			cur_node = new_node;
		}else{
			cur_node = next_node;
		}
	}
	if(cur_node!=&trie){
		// string end
		cur_node->done = 1;
	}
}

int trie_search(const char data[])
{
	int i;
	trie_type *cur_node = &trie;
	trie_type *next_node;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node = cur_node->child[data[i]-'a'];
		if( next_node == 0 ){
			// empty child 
			return 0;
		}else{
			cur_node = next_node;
		}
	}
	if(cur_node!=&trie){
		if (cur_node->done==1) return 1;
	}
	return 0;
}

int main()
{
	init();
	trie_insert("abc");
	trie_insert("ksg");
	trie_insert("abefg");
	trie_insert("tg");
	
	printf("%d\n",trie_search("abf"));//0
	printf("%d\n",trie_search("ksg"));//1
	printf("%d\n",trie_search("abdfg"));//0
	printf("%d\n",trie_search("abefg"));//1
	printf("%d\n",trie_search("ab"));//0
	
	init();
	trie_insert("abcadfae");
	trie_insert("ksasdfg");
	trie_insert("abadfefg");
	trie_insert("tgadf");
	
	printf("%d\n",trie_search("abf"));//0
	printf("%d\n",trie_search("ksasdfg"));//1
	printf("%d\n",trie_search("abdfg"));//0
	printf("%d\n",trie_search("abadfefg"));//1
	printf("%d\n",trie_search("ab"));//0
	
	init();
}

코드 설명

dfs_free 함수에서는 자식들이 있는지 먼저 확인한뒤 재귀 호출로 자식들의 메모리 해제를 요청하게 됩니다.

	for(i=0;i<ALPHA;i++){
		child_node = cur_node->child[i];
		if( child_node != 0 ){
			dfs_free(child_node);
		}
	}

현재 노드의 메모리는 다음 줄에서 해제가 됩니다.

	if( &trie==cur_node ){
		for(i=0;i<ALPHA;i++){
			cur_node->child[i] = 0;
		}
		cur_node->done = 0;
	}else{
		free(cur_node);
	}

최상위 노드는 root node로 해제를 하지 않습니다. 다만 자식들을 가리키고 있던 포인터만 초기화 합니다.

최상위 노드가 아니라면 실제 메모리를 해제하고 return하게 됩니다.

2021년 4월 18일 일요일

TRIE (정적 메모리로 구현)

TRIE 기본 개념은 많은곳에서 자료를 구할 수 있으므로 자세한 설명은 여기에 기록 하지 않습니다.

WIKI 참고 바랍니다.

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

장점

- HASH를 대체할 수 있다.

- 충돌이 일어나지 않는다.

- 사전순 정렬이 되어있다.

단점

- 단순 조회는 HASH보다 느릴 수 있음

- 메모리 사용량이 많음

C언어로 구현한 코드는 map이나 dictionary가 없기 때문에 배열을 이용한 index(문자-'a')로 예제가 되어있습니다.

typedef struct {
int child[ALPHA];
int done;
}trie_type;

Wiki 설명예제 python 코드에서는 Dict 예제로 되어있는점 참고바랍니다.

self.children: Dict[str, Node] = {}  # 문자를 노드로 대응

전체 코드

#include <stdio.h>

#define ALPHA 26
#define MAX_TRIE_VERTEX 100

typedef struct {
	int child[ALPHA];
	int done;
}trie_type;

trie_type trie[MAX_TRIE_VERTEX];
int trie_count = 1;

int init()
{
	int i,j;
	trie_count = 1; // for root node
	for(i=0;i<MAX_TRIE_VERTEX;i++){
		for(j=0;j<ALPHA;j++){
			trie[i].child[j] = 0;
		}
		trie[i].done = 0;
	}
}

void trie_insert(const char data[])
{
	int i;
	int node_vertex = 0; // 0 : root node
	int next_node_vertex = 0;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node_vertex = trie[node_vertex].child[data[i]-'a'];
		if( next_node_vertex == 0 ){
			// empty chiled need to add
			trie[node_vertex].child[data[i]-'a'] = trie_count;
			node_vertex = trie_count;
			trie_count++;
		}else{
			node_vertex = next_node_vertex;
		}
	}
	if(node_vertex!=0){
		// string end
		trie[node_vertex].done = 1;
	}
}

int trie_search(const char data[])
{
	int i;
	int node_vertex = 0; // 0 : root node
	int next_node_vertex = 0;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node_vertex = trie[node_vertex].child[data[i]-'a'];
		if( next_node_vertex == 0 ){
			// empty child 
			return 0;
		}else{
			node_vertex = next_node_vertex;
		}
	}
	if(node_vertex!=0){
		if (trie[node_vertex].done==1) return 1;
	}
	return 0;
}

int main()
{
	init();
	trie_insert("abc");
	trie_insert("ksg");
	trie_insert("abefg");
	trie_insert("tg");
	
	printf("%d\n",trie_search("abf"));//0
	printf("%d\n",trie_search("ksg"));//1
	printf("%d\n",trie_search("abdfg"));//0
	printf("%d\n",trie_search("abefg"));//1
	printf("%d\n",trie_search("ab"));//0
}

위 내용은 정적 메모리로 구현되어 있습니다. 다음 노드의 배열을 아래와 같은 코드로 구현하여 indexing이 빠르게 됩니다. 이 부분을 일일이 loop를 사용하여 확인한다면 성능이 떨어지게 됩니다.

next_node_vertex = trie[node_vertex].child[data[i]-'a'];

코드 간단설명

trie_insert 함수에서 문자열이 입력되면 문자열을 하나씩 확인하면서 node를 찾아갑니다.

node가 없다면 새로운 노드를 추가하게 됩니다.

마지막은 done flag를 추가해서 문자열이 끝남을 기록해 둡니다.

done flag는 필요에 따라 유용하게 사용가능합니다.

2021년 4월 11일 일요일

나머지 연산 % (modulo) 특징

SW작업시 간혹 나머지 (C언어 %) 연산을 사용하는 경우가 있습니다.

대표적으로 연산결과가 특정값을 넘어가지 않게 하기 위함이죠. 주어진 배열을 넘어가지 않도록 하기 위함인데, 그것 외에도 연산을 여러번 하면서 특정값을 유지하고 싶은때가 있습니다.

예를 들어보자면 계산 결과가 굉장히 큰 연산이 있습니다. 중간에 overflow되기도 하고요. 그렇다면 최종 결과에 % 연산과 중간 중간에 %연산을 한 경우 결과가 어떻게 될까요?

https://opentutorials.org/module/1544/9532

위 링크 아래 내용 참고하면 + , * 연산에 대해서 항상 참이 됩니다.

나머지의 법칙

나머지 연산은 기본적으로 결합, 분배, 교환법칙이 모두 성립하지 않습니다. 그래서 사용할때에 항상 계산순서와 위치에 주의를 해야합니다. 단 나머지 연산에서 성립하는 독특한 성질들도 있습니다.

a를 b로 나눈 나머지를 a mod b = a % b라고 표현하기로 합시다. 이 때 나머지는 다음과 같은 식들이 항상 성립합니다.

( a + m ) % m = a % m

( (a % m) + ( b % m) ) % m = ( a + b ) % m

( ( a % m) * ( b % m) ) % m = ( a * b) % m

막상 해보면 맞는것 같지만, programming 할때 주의해야할 점이 있습니다.

단순 계산에서는 문제가 없습니다. C언어로 구현한 SW를 살펴보도록 하겠습니다.

// mod
#include <stdio.h>

#define MOD 34502
void test1()
{
	int i,a,b;
	for(i=0;i<0x7ffffff0;i++){
		a = (i*34500)%MOD;
		b = ((i%MOD)*34500)%MOD;
		if (a!=b) {
			printf("t1 i=%d, %d %d\n",i,a,b);
			printf("error\n");
			break;
		}
	}
}
void test2()
{
	unsigned int i,a,b;
	for(i=0;i<0x7ffffff0;i++){
		a = (i*34500)%MOD;
		b = ((i%MOD)*34500)%MOD;
		if (a!=b) {
			printf("t2 i=%d, %d %d\n",i,a,b);
			printf("error\n");
			break;
		}
	}
}
int main()
{
	printf("%d\n",sizeof(int));
	test1();
	test2();
	return 0;
}

테스트하면 아래와 같습니다.

4
t1 i=62246, -6812 13516
error
t2 i=124492, 6704 27032
error

이렇게 되는 사유는 중간에 overflow가 일어나기 때문입니다.

결론은 중간식이 overflow가 되지 않도록 관리가 필요하고 + 연산에 대해서만 동작합니다. overflow가 되어서 - 연산이 이루어지지 않도록 해야 합니다.

2021년 4월 4일 일요일

문자열의 정렬 (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
 
#include <stdio.h>
 
#define N_MAX 10
 
int data[]={9,3,1,4,5,3,4,6,2,4};
 
void swap(int i,int j)
{
    int temp;
    temp = data[i];
    data[i]=data[j];
    data[j]=temp;
}
 
void print()
{
    int i;
    for(i=0;i<N_MAX;i++){
        printf("%d ",data[i]);
    }
    printf("\n");
}
 
int main()
{
    int i,j;
    for(i=0;i<N_MAX;i++){
        for(j=i+1;j<N_MAX;j++){
            if(data[i]>data[j]){
                swap(i,j);
            }         
        }
    }
    
    print();
    return 0;
}
Colored by Color Scripter
cs

실행화면

1
1 2 3 3 4 4 4 5 6 9
cs

이것을 문자열 정렬로 변환해보겠습니다.

방법은 2가지가 있습니다.

1. 실제 데이터를 변경하는 방법

2. 데이터를 변경하지 않고 인덱스만 정렬하는 방법

먼저 1번에 대해서 알아보겠습니다.

선행 지식으로 두가지를 알아야 합니다.

1. 문자열의 비교 방법 - strcmp 함수를 사용하던가 직접 만들어야합니다.

2. 문자열 복사

문자열 정렬 - 실제 데이터를 변경하는 방법

위의 정수 정렬에서 조건 검사를 하는 부분은 아래와 같습니다.

if(data[i]>data[j]){

이것은 아래와 같이 변경도 가능합니다. 중학교 수준의 방정식입니다.

if(data[i]-data[j]>0){

그럼 정수의 뺄셈을 해주는 diff 함수가 존재한다면 아래와 같이 변형이 가능합니다.

if(diff(data[i],data[j])>0){

문자열에서도 위와 같이 동일한 함수를 사용합니다.

문자열 비교 함수 diff 는 값이 클때는 +값 작을때는 - 값 같을때는 0 을 리턴하도록 제작합니다.

diff 함수를 사용하는곳은 위에서 한 곳 뿐인데 0보다 큰지 작은지의 결과만 사용하므로 제작은 1,0,-1이 넘어가도록 제작합니다.

1
2
3
4
5
6
7
8
9
10
11
int diff(char *a,char *b){
    int i;
    for(i=0;;i++){
        if(a[i]==0 && b[i]==0)return 0;
        if(a[i]==0)return -1;
        if(b[i]==0)return 1;
        if(a[i]-b[i]>0)return 1;
        if(a[i]-b[i]<0)return -1;
    }
    return 0;
}
Colored by Color Scripter
cs

만들어보면 위와 같습니다. 인자는 문자열을 받고 각각의 데이터가 같이 않는동안 for loop를 돌게 됩니다.

문자열 복사도 아래와 같이 만들었습니다.

1
2
3
4
5
6
7
8
void cpy(char *dst,char *src)
{
    int i;
    for(i=0;;i++){
        dst[i] = src[i];
        if(dst[i]==0)break;
    }
}
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
 
#include <stdio.h>
 
#define N_MAX 10
 
char data[N_MAX][80]={
    "hello","abc","a","cdef","cdef","zzzz","bbb","ba","bc","ab"
    };
 
int diff(char *a,char *b){
    int i;
    for(i=0;;i++){
        if(a[i]==0 && b[i]==0)return 0;
        if(a[i]==0)return -1;
        if(b[i]==0)return 1;
        if(a[i]-b[i]>0)return 1;
        if(a[i]-b[i]<0)return -1;
    }
    return 0;
}
void cpy(char *dst,char *src)
{
    int i;
    for(i=0;;i++){
        dst[i] = src[i];
        if(dst[i]==0)break;
    }
}
void swap(int i,int j)
{
    char temp[80];
    cpy(temp,data[i]);
    cpy(data[i],data[j]);
    cpy(data[j],temp);
}
 
void print()
{
    int i;
    for(i=0;i<N_MAX;i++){
        printf("%s\n",data[i]);
    }
}
 
int main()
{
    int i,j;
    for(i=0;i<N_MAX;i++){
        for(j=i+1;j<N_MAX;j++){
            if(diff(data[i],data[j])>0){
                swap(i,j);
            }
        }
    }
    
    print();
    return 0;
}
Colored by Color Scripter
cs

실행 결과

1
2
3
4
5
6
7
8
9
10
a
ab
abc
ba
bbb
bc
cdef
cdef
hello
zzzz
cs

정수 정렬과 문자열 정렬을 비교해보면, 비교 함수와 swap함수만 제작하면 됩니다.

또 다른 인덱스만 정렬하는것은 다음에 작성하도록 하겠습니다.

2021년 3월 27일 토요일

[C언어] graph 탐색 BFS 인접 행렬

이전에 작성한 linked list 소스를 이해가 쉽게 인접 행렬로 구현함

인접 행렬

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
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 20
 
int adj_matrix[MAX_VERTICES+1][MAX_VERTICES+1];
int visited[MAX_VERTICES+1];
 
void graph_init()
{
    int vi,vo;
    for (vi = 0; vi<MAX_VERTICES; vi++){
        for (vo = 0; vo<MAX_VERTICES; vo++){
            adj_matrix[vi][vo] = 0;
        }
        visited[vi] = 0;
    }
}
 
void insert_edge(int u, int v)
{
    // 간선 정보 u->v
    adj_matrix[u][v]=1;
}
 
// 간단 queue
typedef int element;
int  front, rear;
element  queue[MAX_VERTICES+2];
 
void init()
{
    front = rear = 0;
}
 
int is_empty()
{
    return (front == rear);
}
 
void enqueue(element item)
{
    rear++;
    queue[rear] = item;
}
 
element dequeue()
{
    front++;
    return queue[front];
}
 
// BFS 이해가 쉽게 인접 행렬로 구현
void bfs_list(int v)
{
    int w;
    init();
    visited[v] = TRUE;
    printf("%d ", v); 
    enqueue(v);
    while (!is_empty()) {
        v = dequeue();
        for (w = 0; w < MAX_VERTICES; w++ ){
            if (adj_matrix[v][w]==1 && !visited[w]) {
                visited[w] = TRUE;
                printf("%d ", w);
                enqueue(w);
            }
        }
    }
}
 
main()
{
    int i;
 
    graph_init();
 
    insert_edge(1, 9);
    insert_edge(1, 5);
    insert_edge(1, 2);
    insert_edge(2, 3);
    insert_edge(3, 4);
    insert_edge(5, 8);
    insert_edge(5, 6);
    insert_edge(6, 7);
    insert_edge(9, 10);
    bfs_list(1);
}
Colored by Color Scripter
cs

bfs_list(1)에서 1은 출발 정점

결과

1
1 2 5 9 3 6 8 10 4 7
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
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 20
#define MAX_ALIST    20
 
typedef struct{
    int in;
    int out;
}adj_info;
 
adj_info adj_alist[MAX_ALIST+1];
int edge_count = 0;
 
int visited[MAX_VERTICES+1];
 
void graph_init()
{
    int i;
    for (i = 0; i<MAX_ALIST; i++){
        adj_alist[i].in = 0;
        adj_alist[i].out = 0;
    }
    edge_count=0;
}
 
void insert_edge(int u, int v)
{
    // 간선 정보 u->v
    adj_alist[edge_count].in = u;
    adj_alist[edge_count].out = v;
    edge_count++;
}
 
// 간단 queue
typedef int element;
int  front, rear;
element  queue[MAX_VERTICES+2];
 
void init()
{
    front = rear = 0;
}
 
int is_empty()
{
    return (front == rear);
}
 
void enqueue(element item)
{
    rear++;
    queue[rear] = item;
}
 
element dequeue()
{
    front++;
    return queue[front];
}
 
// BFS 이해가 쉽게 인접 행렬로 구현
void bfs_list(int v)
{
    int w;
    init();
    visited[v] = TRUE;
    printf("%d ", v); 
    enqueue(v);
    while (!is_empty()) {
        v = dequeue();
        for (w = 0; w < edge_count; w++ ){
            if (adj_alist[w].in==v && !visited[adj_alist[w].out]) {
                visited[adj_alist[w].out] = TRUE;
                printf("%d ", adj_alist[w].out);
                enqueue(adj_alist[w].out);
            }
        }
    }
}
 
main()
{
    int i;
 
    graph_init();
 
    insert_edge(1, 9);
    insert_edge(1, 5);
    insert_edge(1, 2);
    insert_edge(2, 3);
    insert_edge(3, 4);
    insert_edge(5, 8);
    insert_edge(5, 6);
    insert_edge(6, 7);
    insert_edge(9, 10);
    bfs_list(1);
}
Colored by Color Scripter
cs

결과

1
1 9 5 2 10 8 6 3 7 4
cs

기존 대비 BFS 내부의 연결된 간선 선택하는 부분이 변경되었습니다.

출력 결과는 이전과 다르지만 오른쪽 왼쪽 가운데 순서는 관계없고 level 단위로 처리만 되면 BFS이며 이것도 BFS 결과입니다.