문제

이진 탐색트리의 삽입, 삭제, 탐색, 순회 및 출력 기능을 바탕으로 학생의 이름과 전화번호를 관리하는 이진탐색트리를 구현하라.


풀이

각 기능을 수행하는 함수는 책에서 학습 할 수 있지만 삭제 함수의 경우, 제가 갖고있는 2권의 자료구조책에는 삭제함수를 반복문으로 구현했는데, 물론 기능적인 면에서 순환방식보다 빠르고 효율적이지만 코드가 복잡하고, 혼자서 머릿속으로 구현하기가 힘든 것 같아 순환방법의 구현을 공부했습니다.

구현 면에서는 반복문보다 순환호출이 더 이해와 구현이 쉬운 것 같습니다.

주의할 것은 삭제함수에 if문이 많은데 각 경우를 if로 표현하면 학생 정보를 삭제하고 출력 시 원하지 않는 결과가 나올 수 있습니다. 

반드시 if~ else if ~ else 문으로 함수를 작성해야합니다. 



그리고 가끔 이런 학생정보 관리 프로그램이나 사전 프로그램 등을 구현하다보면 꼭 공백이나 엔터키가 말썽을 부렸는데

다행히 아래 코드처럼 작성하니 엔터키 관련해서는 오류가 뜨지않았습니다.

133~134행을 주석 처리 후 135~136행을 작성 후 실행 하면 원하는 기능의 알파벳 입력 시 한글을 입력하면 엔터키 오류가 뜹니다.



코드

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
// 이진 탐색 트리를 사용한 영어 사전
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
 
#define MAX_WORD_SIZE     100
#define MAX_MEANING_SIZE 200
 
// 데이터 형식
typedef struct {
    char name[MAX_WORD_SIZE];        // 키필드
    char number[MAX_MEANING_SIZE];
} element;
// 노드의 구조
typedef struct TreeNode {
    element key;
    TreeNode* left, * right;
} TreeNode;
 
// 만약 e1 < e2 이면 -1 반환
// 만약 e1 == e2 이면 0 반환
// 만약 e1 > e2 이면 1 반환
int compare(element e1, element e2)
{
    return strcmp(e1.name, e2.name);
}
// 이진 탐색 트리 출력 함수
void display(TreeNode* p)
{
    if (p != NULL) {
        //printf("(");
        display(p->left);
        printf("이름:%s\n전화번호%s\n", p->key.name, p->key.number);
        display(p->right);
        //printf(")");
    }
}
// 이진 탐색 트리 탐색 함수
TreeNode* search(TreeNode* root, element key)
{
    TreeNode* p = root;
    while (p != NULL) {
        if (compare(key, p->key) == 0)
            return p;
        else if (compare(key, p->key) < 0)
            p = p->left;
        else if (compare(key, p->key) > 0)
            p = p->right;
    }
    return p;     // 탐색에 실패했을 경우 NULL 반환
}
TreeNode* new_node(element item)
{
    TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
TreeNode* insert_node(TreeNode* node, element key)
{
    // 트리가 공백이면 새로운 노드를 반환한다. 
    if (node == NULL) return new_node(key);
 
    // 그렇지 않으면 순환적으로 트리를 내려간다. 
    if (compare(key, node->key) < 0)
        node->left = insert_node(node->left, key);
    else if (compare(key, node->key) > 0)
        node->right = insert_node(node->right, key);
    // 루트 포인터를 반환한다. 
    return node;
}
TreeNode* min_value_node(TreeNode* node)
{
    TreeNode* current = node;
    // 맨 왼쪽 단말 노드를 찾으러 내려감
    while (current->left != NULL)
        current = current->left;
    return current;
}
// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 
// 새로운 루트 노드를 반환한다. 
TreeNode* delete_node(TreeNode* root, element key)
{
    if (root == NULL) return root;
 
    // 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
    if (compare(key, root->key) < 0)
        root->left = delete_node(root->left, key);
    // 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
    else if (compare(key, root->key) > 0)
        root->right = delete_node(root->right, key);
    // 키가 루트와 같으면 이 노드를 삭제하면 됨
    else {
        // 첫 번째나 두 번째 경우
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 세 번째 경우
        TreeNode* temp = min_value_node(root->right);
 
        // 중외 순회시 후계 노드를 복사한다. 
        root->key = temp->key;
        // 중외 순회시 후계 노드를 삭제한다. 
        root->right = delete_node(root->right, temp->key);
    }
    return root;
}
 
//
void help()
{
    printf("삽입(i), 탐색(s),프린트(p), 삭제(d): ");
}
// 이진 탐색 트리를 사용하는 영어 사전 프로그램 
int main(void)
{
    char command;
    element e;
    TreeNode* root = NULL;
    TreeNode* tmp;
 
    while(1){
        help();
        //command = getchar();
        //getchar();        // 엔터키 제거
        scanf(" %c", &command);
        getchar();
        switch (command) {
        case 'i':
            printf("친구의 이름: ");
            scanf(" %s", e.name);
            getchar();
            printf("친구의 전화번호: ");
            scanf(" %s", e.number);
            getchar();
            root = insert_node(root, e);
            break;
        case 'd':
            printf("이름:");
            scanf(" %s", e.name);
            getchar();
            root = delete_node(root, e);
            break;
        case 'p':
            display(root);
            printf("\n");
            break;
        case 's':
            printf("친구의 이름:");
            scanf(" %s", e.name);
            getchar();
            tmp = search(root, e);
            if (tmp != NULL)
                printf("%s의 전화번호:%s\n",tmp->key.name, tmp->key.number);
            else
                printf("데이터가 존재하지 않습니다.\n");
            break;
        case 'q':return 0;
        default: 
            printf("잘못입력습니다.재입력하세요\n");
 
        }
 
    }/* while (command != 'q');*/
    return 0;
}
cs


결과





저작자표시

'과제 > 자료구조' 카테고리의 다른 글

#5. 단순연결리스트를 이용한 정렬리스트 만들기  (0) 2020.04.22
#4. 수식을 후위식으로 변환하고 계산하기  (2) 2020.04.11
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25


문제

단순연결리스트를 이용해서 숫자를 삽입할 때 마다 오름차순으로 정렬되게 끔 하는 간단한 프로그램을 만드시오.

조건: 아래의 추상 자료형(ADT) 함수를 모두 이용하여 5개이상의 원소를 삽입할 것



풀이

중요한 부분이 총 3가지라고 생각합니다. (글로는 설명이 힘들어서 소스코드만 올립니다..)

1. 삽입함수

정확한 이해가 필요했습니다. 삽입할 때 마다 정렬되게끔 하려면 몇가지 경우를 고려해야하는데 ,

작은 단위( 원소가 하나일 때, 두개 일 때, 3개일 때 ..) 부터 노트에 그려서 규칙을 찾아보면 의외로 간단합니다.

2. 삭제함수

Delete함수는 대충 책에서도 비슷하게 설명이 되있기 때문에 조금만 생각해보면 되지만 Clear함수는 원소를 삭제하면서 

그 위치를 기억하는 temp변수가 필요하다는 아이디어를 구현하는데 시간을 많이 썼습니다. 

단순히 removed함수만을 이용해서 삭제과정을 거치면 free하는 과정에서 연결리스트가 끊겨버리므로 실행 시 오류가 뜹니다.


3. 리스트의 원소갯수 반환 함수

원소갯수를 필요로하는 함수에 인자로 len을 추가시켜서 즉각즉각 갱신하도록했습니다.

ListNode 구조체에 len변수를 추가하여 사용해보려고 했는데 잘 안풀려서 다시 한번 고민을 해봐야겠습니다.



코드

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
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct ListNode
{
    double data;
    struct ListNode* link;
}ListNode;
void Add(ListNode**list,double item)
{
    ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
    temp->data = item; temp->link = NULL;
    ListNode* pos = *list;
    if (*list == NULL) {
        *list = temp;
    }
    //같은것도 삽입해야하므로"="붙여야함!
    else if (temp->data <= (*list)->data)
        {
        temp->link = *list;
        *list = temp;
        }
    else
    {
        while (1)
        {
             if (pos->link == NULL)
            {
                pos->link = temp;break;
            }
            else if (temp->data < pos->link->data)
            {
                temp->link = pos->link;
                pos->link = temp;
                break;
            }
            //어떤 경우도 아닐 때 ex) 3 4 5 7일때 6삽입
            pos = pos->link;
        }
    }
}
void Delete(ListNode** list, double item,int len)
{
    ListNode* removed;
    if ((*list)->link == NULL)
    {
        free((*list));
        *list = NULL;
    }
    else if ((*list)->data == item)
    {
        removed = *list;
        *list = (*list)->link;
        free(removed);
    }
    else {
        ListNode* pre = *list;
        for (pre; pre->link->data != item; pre = pre->link);
         removed = pre->link;
        pre->link = removed->link;
        free(removed);
    }
    len--;
    
}
void Clear(ListNode** list, int len)
{
    ListNode* removed;
        ListNode* temp = *list;
        while (1)
        {
            removed = temp;
            if (removed == NULL)break;
            *list = (*list)->link;
            temp = temp->link;
            free(removed);
            
        }
}
ListNode* is_in_list(ListNode* list, double item)
{
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        if (temp->data == item)
            return temp;
 
        return temp;
}
int get_length(ListNode* list)
{
    int len = 0;
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        len++;
    return len;
}
int is_empty(ListNode* list)
{
    return list == NULL;
}
void display(ListNode* list)
{
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        printf("%.0lf ", temp->data);
        printf("\n");
}
int main()
{
    double item;
    int len = 0;
    ListNode* head = NULL;
    ListNode* temp = NULL;
    //비었는지 검사, 1:비어있음 0:비어있지않음
    printf("리스트가 비었는지 검사: %d\n", is_empty(head));
    //최초에 무작위숫자 7개를 오름차순으로삽입시킴
    printf("7개의 원소를 삽입합니다.\n");
    for (int i = 0; i < 7; i++) {
        scanf("%lf", &item);
        Add(&head, item);
    }
    printf("리스트의 길이를 출력합니다.%d\n",get_length(head));
    printf("리스트의 모든 요소를 출력합니다.\n");
    display(head);
    //특정 값이 리스트에 있는지 탐색해본다.
        printf("리스트에 존재하는지 조사할 숫자: ");
        scanf("%lf", &item);
        temp = is_in_list(head,item);
        if (temp == NULL)printf("없음\n");
        else printf("%.0lf이(가)있습니다.\n", temp->data);
    
    //리스트에있는 원소중 한개 제거
        printf("리스트의 원소 중 제거하고 싶은 숫자: ");
        scanf("%lf", &item);
        temp = is_in_list(head, item);
        if (temp == NULL)printf("없음\n");
        else
        {
            Delete(&head, temp->data,len);
            printf("제거되었습니다.\n");
        }
        //삭제하고 나서 요소 확인
        printf("리스트의 모든 요소를 출력합니다.\n");
        display(head);
        printf("남아있는 원소의 갯수는 %d개입니다.\n", get_length(head));
        //모두 제거하기 
        printf("리스트의 원소를 모두 제거하겠습니다.\n");
        Clear(&head,len);
        printf("리스트에 남아있는 원소를 출력합니다.\n");
        display(head);
        
        printf("리스트가 비었는지 검사: %d\n", is_empty(head));
}
cs


결과




저작자표시

'과제 > 자료구조' 카테고리의 다른 글

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#4. 수식을 후위식으로 변환하고 계산하기  (2) 2020.04.11
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25

문제

main문에서 주어진 수식을 후위식으로 변환 후 변환 된 수식을 후위계산하여 값을 출력하시오


풀이

수식을 후위식으로 변환하는 함수부터 진행하기 때문에 스택의 요소는 char형 입니다.

일반적인 후위변환식을 작성하고, push,pop,peek등의 스택의 기본적인 연산 함수를 그대로 이용하여 후위계산을 하려면

스택의 요소를 int형으로 바꿔주어야하는데(숫자가 스택에 push되므로) 

스택에 push할 때 char형을 int형으로 형변환하여  push하는 것 외에 일반적인 수식계산 함수와 다를 게 없습니다.


코드

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
// C program to convert infix expression to postfix  
#pragma warning(disable:4996)
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
 
// Stack type 
struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};
 
// Stack Operations 
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
 
    if (!stack)
        return NULL;
 
    stack->top = -1;
    stack->capacity = capacity;
 
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
 
    return stack;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}
 
 
// A utility function to check if the given character is operand 
int isOperand(char ch)
{
  
    return (ch >= '0' && ch <= '9');
}
 
// A utility function to return precedence of a given operator 
// Higher returned value means higher precedence 
int Prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-':
        return 1;
 
    case '*':
    case '/':
        return 2;
 
    case '^':
        return 3;
    }
    return -1;
}
 
 
// The main function that converts given infix expression 
// to postfix expression.  
void infixToPostfix(char* exp)
{
    int i, k;
 
    // Create a stack of capacity equal to expression size  
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) // See if stack was created successfully  
        return;//오류 
 
    for (i = 0, k = -1; exp[i]; ++i)
    {
        // If the scanned character is an operand, add it to output. 
        if (isOperand(exp[i]))
            exp[++k] = exp[i];
 
        // If the scanned character is an ‘(‘, push it to the stack. 
        else if (exp[i] == '(')
            push(stack, exp[i]);
 
        // If the scanned character is an ‘)’, pop and output from the stack  
        // until an ‘(‘ is encountered. 
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return; // invalid expression         //오류      
            else
                pop(stack);
        }
        else // an operator is encountered 
        {
            while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }
 
    }
 
    // pop all the operators from the stack 
    while (!isEmpty(stack))
        exp[++k] = pop(stack);
 
    exp[++k] = '\0';
    printf("%s\n", exp);
    
 
}
int eval(char* exp)
{
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) // See if stack was created successfully  
        exit(1);
    int op1, op2, n;
    char ch;
    n = strlen(exp);
    for (int i = 0; i < n; i++)
    {
        ch = exp[i];
        //숫자일 떄
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/')
            push(stack, ch-'0');
        else
        {
            op2 = pop(stack);
            op1 = pop(stack);
            switch (ch)
            {
            case '+': push(stack, op1 +op2); break;
            case '-':push(stack, op1 -op2); break;
            case '*':push(stack, op1 *op2); break;
            case '/':push(stack, op1 /op2); break;
            }
        }
    }
    return pop(stack);
}
// Driver program to test above functions 
int main()
{
    int result;
    char exp[] = "3+4/4*3-2*2";
    infixToPostfix(exp);
    
    result=eval(exp);
    printf("결과값은 %d입니다.\n", result);
    return 0;
}
 
 
cs


결과





저작자표시

'과제 > 자료구조' 카테고리의 다른 글

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#5. 단순연결리스트를 이용한 정렬리스트 만들기  (0) 2020.04.22
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25

문제

5명의 학생들 중 입력된 학번, 이름, 성적 중 학생의 성적을 기준으로 내림차순으로 구현하되

해당 학번의 학생 정보 전체가 아래와 같이 정렬되도록 순환함수를 이용해 구현하시오.

 

 

 

풀이

주의) 제 소스코드는 자료구조 교재 끝부분에 배우는 정렬 단원의 "퀵정렬"을 이용한 코드입니다. 학교진도에 맞춰서 공부하신다면 1,2,3,4,5일 때 모두 하나씩 비교해가며 5,4,3,2,1 로 만드는 방법으로 구현해보시는게 좋을 것 같습니다.

교수님께서 주신 기본 코드를 유지하면서 순환을 이용하여 해결할 수 있도록 퀵정렬로 풀었습니다.

추가점수 옵션으로 구조체 배열대신 구조체 포인터 변수로 동적할당받아서 해결하는 조건이 있어서

84행을 85행으로 고쳐서 풀었습니다. 연산이 종료되고 동적할당을 free했습니다!

 

 

코드

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
#pragma warning(disable:4996)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#define MAX 5
 
typedef struct student
{
    int student_no; //학번
    char name[40]; //이름
    int score; //성적
}student;
 
//배열 교환
void SWAP(student* arr, int a, int b)
{
    //한 배열이 뭉탱이로 옮겨짐.(정보갱신)
    student temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
// 배열, 하한, 상한)
void SORT(student* arr, int m, int n, int choice)
{
    //선택 옵션이 1이면 성적순 내림차순정렬
        if (choice == 1)
        {
            if (m < n)
            {
                int key = m;
                int i = m + 1;
                int j = n;
                //엇갈리지 않을동안
                while (i <= j)
                {
                    while (i <= n && arr[i].score >= arr[key].score)
                        i++;
                    while (j > m&& arr[j].score <= arr[key].score)
                        j--;
                    //엇갈리면 j와 key값 교체
                    if (i > j)
                        SWAP(arr, j, key);
                    //엇갈리지않으면 i와 j 교체
                    else
                        SWAP(arr, i, j);
                }
                //각각 정렬된 수의 전, 후 에서 똑같이 순환반복
                SORT(arr, m, j - 1,choice);
                SORT(arr, j + 1, n,choice);
            }
        }
        //선택 옵션이 2이면 학번순 내림차순 정렬
        else if (choice == 2)
        {
                if (m < n)
                {
                    int key = m;
                    int i = m + 1;
                    int j = n;
                    //엇갈리지 않을동안
                    while (i <= j)
                    {
                        while (i <= n && arr[i].student_no >= arr[key].student_no)
                            i++;
                        while (j > m&& arr[j].student_no <= arr[key].student_no)
                            j--;
                        //엇갈리면 j와 key값 교체
                        if (i > j)
                            SWAP(arr, j, key);
                        //엇갈리지않으면 i와 j 교체
                        else
                            SWAP(arr, i, j);
                    }
                    //각각 정렬된 수의 전, 후 에서 똑같이 순환반복
                    SORT(arr, m, j - 1, choice);
                    SORT(arr, j + 1, n, choice);
                }
        }
}
int main() {
 
    //student s[MAX];
    student* s = (student*)malloc(sizeof(student) * 5);
    int i = 0;
    //입력받을 옵션변수
    int choice;
    char str[40];
    //stduent information field
    for (i = 0; i < MAX; i++)
    {
        printf("Student Information (학번, 이름, 성적) : ");
        scanf("%d", &s[i].student_no);
        scanf("%s", str);
        strcpy(s[i].name, str);
        scanf("%d", &s[i].score);
    }
    printf("성적순 정렬은 1, 학번순 정렬은 2를입력하세요: ");
    scanf("%d", &choice);
    SORT(s, 0, MAX - 1,choice); //소트(학생 배열,0,num-1)
    for (i = 0; i < MAX; i++)
        printf("%d\t%s\t%d\n", s[i].student_no, s[i].name, s[i].score);
    printf("\n");
    //동적할당 해제
    free(s);
    return 0;
}
 cs

 

저작자표시

'과제 > 자료구조' 카테고리의 다른 글

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#5. 단순연결리스트를 이용한 정렬리스트 만들기  (0) 2020.04.22
#4. 수식을 후위식으로 변환하고 계산하기  (2) 2020.04.11
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25

문제 

10*10 2차원 배열에서 

YELLOW: 2, BLACK: 1, WHITE: 0 으로 설정하여 다음과 같이 칠해진 좌표가 있다고하자.

X표 되어있는 좌표는 0인 상태이고, (4,4)좌표부터 시작해서 순환함수를 이용하여 모든 0인 좌표를 1로 칠하자.


풀이

반복문으로 작성하면 금방이지만 순환함수를 사용하라고했으므로, 좌표의 색깔을 입히는 함수내부에 

시작 좌표부터 각 방향(동서남북)으로 탐색을 시작하여 모든 0인좌표들을찾아서 1로 바꾸는 순환함수를 작성한다.


코드

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
#include <stdio.h>
#define WHITE 0 // 0을 WHITE라 정의
#define BLACK 1 // 1을 BLACK이라 정의
#define YELLOW 2 // 2를 YELLOW라 정의
 
int screen[10][10] = // 배열 초기화 후 바로 초기값을 넣어줍니다.
{ {2,2,2,2,2,2,2,2,2,2},
 {2,2,2,2,2,2,2,2,2,2},
 {2,2,2,0,0,0,0,2,2,2},
 {2,2,2,2,0,0,0,2,2,2},
 {2,2,2,2,0,0,0,2,2,2},
 {2,2,2,2,0,0,0,0,2,2},
 {2,2,2,2,0,2,2,2,2,2},
 {2,2,2,2,0,2,2,2,2,2},
 {2,2,2,2,0,2,2,2,2,2},
 {2,2,2,2,2,2,2,2,2,2} };
 
// screen 배열을 읽어들이기(순환 호출에서 쓰임)
char read_pixel(int x, int y)
{
    return screen[x][y];
}
 
// 해당 x, y 위치를 color(BLACK)로 채우기(순환 호출에서 쓰임)
void write_pixel(int x, int y, int color)
{
    screen[x][y] = color;
}
 
 //영역 채우기 알고리즘 
void flood_fill(int x, int y)
{
    if (read_pixel(x, y) == WHITE) // read_pixel 함수 호출의 결과로 0을 발견하면
    {
        write_pixel(x, y, BLACK); // write_pixel 함수를 호출해서 BLACK(1)로 채우기
        //동
        if (x + 1 < 10)
            flood_fill(x + 1, y);
        //남
        if (y + 1 < 10)
            flood_fill(x, y + 1);
        //서
        if (x - 1 >= 0)
            flood_fill(x - 1, y);
        //북
        if (y - 1 >= 0)
            flood_fill(x, y - 1); 
    }
}
 
void result_print()
{
    int i, j; // 인덱스 i, j 선언
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            printf("%d ", screen[i][j]); // 10x10 크기의 배열 출력(보여주기)
        }
        printf("\n");
    }
}
 
int main()
{
 
    printf("영역 채우기 대상 도형\n-------------------\n");
    result_print(); // 초기값으로 지정된 배열을 출력 
 
    flood_fill(4, 4); // 채우기 실행(시작 위치: 4,4)
 
    printf("안쪽을 채우는 순환 호출 함수 작동\n-------------------\n");
    result_print(); // flood_fill 함수 호출 뒤 결과(배열) 출력 
 
    return 0;
}
cs


결과



저작자표시

'과제 > 자료구조' 카테고리의 다른 글

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#5. 단순연결리스트를 이용한 정렬리스트 만들기  (0) 2020.04.22
#4. 수식을 후위식으로 변환하고 계산하기  (2) 2020.04.11
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25

문제

1부터 100만까지 순차적으로 더하는 연산의 수행시간과 다른 덧셈 알고리즘을 이용한 연산의 수행시간을 구하시오


풀이

1부터 100만까지 더하는 반복문을 그대로 작성하고, 저는 n(n+1)/2의 합공식을 이용한 알고리즘으로 풀었습니다. 

 

코드 및 결과


알고리즘1(순차 덧셈)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int main()
{
    clock_t start, end;
    double duration;
    long long sum = 0;
    start = clock();
    for (int i = 1; i <= 1000000; i++)
        sum += i;
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("수행시간은%f초입니다.\n", duration);
    printf("총합은%lld입니다.\n", sum);
}
cs



알고리즘2(합공식)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
long long func(long long n);
int main()
{
    clock_t start, end;
    double duration;
    long long sum = 0;
    start = clock();
    sum = func(1000000);
    end = clock();
    duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf("수행시간은%f초입니다.\n", duration);
    printf("총합은%lld입니다.\n", sum);
}
long long func(long long n)
{
    return n * (n + 1) / 2;
}
cs




저작자표시

'과제 > 자료구조' 카테고리의 다른 글

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#5. 단순연결리스트를 이용한 정렬리스트 만들기  (0) 2020.04.22
#4. 수식을 후위식으로 변환하고 계산하기  (2) 2020.04.11
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25

+ Recent posts

티스토리툴바