How We Coding

180301 튜터링 - 트리(Tree)

Tutoring/17-2 Data Structure (Winter)2018. 3. 2. 00:35

< 180301 >


- 트리 : 계층 구조를 표현하는 비선형 자료구조


- 용어 : 노드(부모, 자식, 형제), 공집합 노드, 단말노드(리프, 터미널), 루트, 서브트리, 레벨, 높이


- 트리의 종류 : 일반트리, 이진트리(Binary Tree)


- 이진트리의 정의 : 모든 노드가 2개의 서브트리를 가지고 있는 트리. (서브트리는 공집합일 수 있다.)


- 이진트리의 성질

>> 노드 수 = 간선 수 + 1

>> 레벨에 따른 최소, 최대 노드를 구할 수 있다.

>> 노드가 n개 일때, 최대 레벨은 n, 최소 레벨은 ceil(log(n+1))


- 이진트리의 종류 : 완전, 포화

>> 완전 이진트리 : 레벨에 따라 왼쪽에서 오른쪽으로 순차적으로 노드가 삽입된 트리

>> 포화 이진트리 : 각 레벨에 노드가 가득 차 있는 이진 트리.



- 이진 트리의 표현


1) 배열을 이용한 구현

>> 주로 힙(Heap)에서 사용

>> 구현의 편의상 0번째 인덱스를 사용하지 않는 경우가 많은 것 같다.

>> 현재노드 기준, 부모노드의 인덱스는 현재노드의 인덱스 / 2

>> 현재노드 기준, 왼쪽 자식의 인덱스는 현재노드의 인덱스 * 2

>> 현재노드 기준, 오른쪽 자식의 인덱스는 현재노드의 인덱스 * 2 + 1


2) 링크 표현


1
2
3
4
5
typedef struct TreeNode {
   int data;
   struct TreeNode * left;
   struct TreeNode * right;
} TreeNode;
cs


>> 노드는 이런식으로 디자인을 한다.



- 트리의 구현 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)


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
// Tree
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct TreeNode {
   int data;
   struct TreeNode * left;
   struct TreeNode * right;
} TreeNode;
 
TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) {
   TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode));
   tmp->data = data;
   tmp->left = left;
   tmp->right = right;
   return tmp;
}
 
void preorderPrint(TreeNode * root) {
   if (root) {
      printf("%d ", root->data);
      preorderPrint(root->left);
      preorderPrint(root->right);
   }
}
 
void inorderPrint(TreeNode * root) {
   if(root){
      inorderPrint(root->left);
      printf("%d ", root->data);
      inorderPrint(root->right);
   }
}
 
void postorderPrint(TreeNode * root) {
   if(root) {
      postorderPrint(root->left);
      postorderPrint(root->right);
      printf("%d ", root->data);
   }
}
 
int nodeCount(TreeNode * root) {
   int count = 0;
   if (root) count = nodeCount(root->left) + nodeCount(root->right) + 1;
   return count;
}
 
int height(TreeNode * root) {
   int count=0;
 
   if (root) {
       int L = height(root->left);
       int R = height(root->right);
       count = (L > R ? L : R) + 1;
   }
   return count;
}
 
void clear(TreeNode * root) {
   if (root) {
      clear(root->left);
      clear(root->right);
      free(root);
   }
}
 
 
// QUEUE
typedef struct queue {
   TreeNode * data[MAX];
   int front;
   int rear;
} Queue;
 
void init(Queue * q) {
   q->front = 0;
   q->rear = 0;
}
 
int isEmpty(Queue * q) {
   return (q->front == q->rear);
}
 
int isFull(Queue * q) {
   return (q->rear + 1) % MAX == q->front;
}
 
void enqueue(Queue * q, TreeNode * data) {
   if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
   else {
      q->rear = (q->rear + 1) % MAX;
      q->data[q->rear] = data;
   }
}
 
TreeNode* peek(Queue * q) {
   if (isEmpty(q)) {
      printf("(peek)큐가 비어있습니다. : ");
      return NULL;
   }
   return q->data[(q->front + 1) % MAX];
}
 
void dequeue(Queue * q) {
   if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
   else {
      q->front = (q->front + 1) % MAX;
   }
}
 
 
 
void level(TreeNode * root) {
   Queue q;
   init(&q);
 
   if (root) {
      enqueue(&q, root);
   }
 
   while (!isEmpty(&q)) {
      TreeNode * tmp = peek(&q); dequeue(&q);
      printf("%d ", tmp->data);
      if (tmp->left) enqueue(&q, tmp->left);
      if (tmp->right) enqueue(&q, tmp->right);
   }
}
 
 
int main()
{
   TreeNode * t8 = makeTreeNode(8, NULL, NULL);
   TreeNode * t4 = makeTreeNode(4, t8, NULL);
   TreeNode * t5 = makeTreeNode(5, NULL, NULL);
   TreeNode * t6 = makeTreeNode(6, NULL, NULL);
   TreeNode * t7 = makeTreeNode(7, NULL, NULL);
   TreeNode * t2 = makeTreeNode(2, t4, t5);
   TreeNode * t3 = makeTreeNode(3, t6, t7);
   TreeNode * t1 = makeTreeNode(1, t2, t3);
 
   TreeNode * root = t1;
 
   preorderPrint(root);
   printf("\n");
   
   inorderPrint(root);
   printf("\n");
   
   postorderPrint(root);
   printf("\n");
 
   printf("노드 갯수 : %d개\n", nodeCount(root));
   printf("depth : %d\n", height(root));
 
   level(root);
 

}
 
cs


>> makeTreeNode() : 첫번째 인자로는 데이터를, 

     두번째 인자는 왼쪽 서브트리의 루트가 될 노드(의 주소)를, 

     세번째 인자로는 오른쪽 서브트리의 루트가 될 노드(의 주소)를 전달한다.


>> 21-27 : 전위순회 코드이다. 전위순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 탐색을 한다.

>> 29-35 : 중위순회 코드이다. 중위순회는 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 탐색을 한다. 

>> 37-43 : 후외순회 코드이다. 후위순회는 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 탐색을 한다.


>> 45-49 : 노드의 갯수를 구하는 함수로 

                  왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 자기 자신의 갯수를 포함한 것이 트리의 노드의 갯수가 된다

>> 51-60 : 트리의 높이를 구하는 함수로

                  왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 중 큰 값에 자기 자신이 높이(1)를 더한 것의 트리의 높이가 된다.

>> 62-68 : 트리의 모든 노드를 삭제하는 함수. 후위순회로 진행하면 된다. 다른 순회로 하면 왜 안되는지도 생각해보자.


>> 116-130 : 트리의 레벨 순회.

                    큐가 필요하다. 또한 TreeNode의 포인터를 담아야 하므로,  73 라인에서 보는 것 처럼 큐의 데이터 타입을 TreeNode* 로 변경하였다.

                    알고리즘은 다음과 같다.

1) 우선 루트를 큐에 담는다.

2) 큐가 비어 있지 않을때까지 루프를 돈다.

3) 큐에 있는 노드 하나를 꺼내 해당 데이터를 출력한다.

4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다.


>> 135-142 : 트리를 생성하는 과정이다.


### BST 는 아마 언젠가 업데이트를 할거 같아. 시간은 걸리겠지만, 하게되면 알려줄게. 여기까지 따라오느라 다들 수고 많았어!!

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06

180301 튜터링 - 큐(Queue)

Tutoring/17-2 Data Structure (Winter)2018. 3. 1. 23:21

< 180301 >




- Queue 정의 : 먼저 들어온 데이터가 먼저 꺼내지는 자료구조


- 예시 : 버스에서 줄서기(앞에 선 사람이 먼저 탐), 

            스타크래프트 게이트웨이(질럿, 드라군, 다크 순으로 찍으면 질럿, 드라군, 다크 순으로 나온다.)



- (선형)큐 구현하기.


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
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int data[MAX];
    int front;
    int rear;
} Queue;
 
void init(Queue * q) {
    q->front = 0;
    q->rear = 0;
}
 
int isEmpty(Queue * q) {
    return (q->front == q->rear);
}
 
void enqueue(Queue * q, int data) {
    q->data[(q->rear)++] = data;
}
 
int peek(Queue * q) {
    if (isEmpty(q)) {
        printf("(peek)큐가 비어있습니다. : ");
        return -11111;
    }
    return q->data[q->front];
}
 
void dequeue(Queue * q) {
    if (!isEmpty(q)) {
        (q->front)++;
    }
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
    dequeue(&q);
 
    printf("%d\n", peek(&q));
}
 
cs


>> 이런식으로 구현할 수 있다.

>> 하지만 이렇게 될 경우, 배열의 앞 공간에 낭비가 발생한다.



- 원형 큐 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)


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>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
   int data[MAX];
   int front;
   int rear;
} Queue;
 
void init(Queue * q) {
   q->front = 0;
   q->rear = 0;
}
 
int isEmpty(Queue * q) {
   return (q->front == q->rear);
}
 
int isFull(Queue * q) {
   return (q->rear+1)%MAX == q->front;
}
 
void enqueue(Queue * q, int data) {
   if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
   else {
      q->rear = (q->rear + 1) % MAX;
      q->data[q->rear] = data;
   }
}
 
int peek(Queue * q) {
   if (isEmpty(q)) {
      printf("(peek)큐가 비어있습니다. : ");
      return -11111;
   }
   return q->data[(q->front+1) % MAX];
}
 
void dequeue(Queue * q) {
   if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
   else {
      q->front = (q->front + 1) % MAX;
   }
}
 
int main()
{
   Queue q;
   init(&q);
 
   enqueue(&q, 1);
   enqueue(&q, 9);
   enqueue(&q, 9);
   enqueue(&q, 8);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
 
   printf("%d\n", peek(&q));
   dequeue(&q);
   
   printf("%d\n", peek(&q));
 

}
cs


>> 사용한 공간의 낭비를 막을 수 있다.

>> 빈 상태와 포화상태를 구분하기 위해 한 칸을 비워둔다. 

>> 21-23 :  포화상태에 대한 코드이다. 모듈러 연산을 통해 마지막 인덱스 다음 인덱스를 0으로 만들 수 있다.



### 연결리스트를 이용한 큐를 만들어보자. 

>> head 포인터를 front 로, tail 포인터를 rear 로 두고 만들면 된다.



### 덱

>> 앞으로도 넣고 뒤로더 넣을 수 있으며, 앞에서도 꺼내고 뒤에서도 꺼낼 수 있다.

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 트리(Tree)  (0) 2018.03.02
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06

180301 튜터링 - 스택의 응용 (수정:180514)

Tutoring/17-2 Data Structure (Winter)2018. 3. 1. 00:35

< 숙제 Review >


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
#include <stdio.h>
#define MAX 100
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s);
int isEmpty(Stack *s);
int isFull(Stack *s);
void push(Stack *s, char data);
char peek(Stack *s);
void pop(Stack *s);
 
int isRightBraket(char *bk)
{
    int idx;
    Stack s;
    init(&s);
 
    for(idx=0; bk[idx]; idx++) {
        char ch = bk[idx];
        if(ch == '{' || ch == '(' || ch == '[') push(&s, ch);
        else {
            char tmp;
            if(isEmpty(&s)) return 0;
            tmp = peek(&s); pop(&s);
            if((tmp == '{' && ch != '}') || (tmp == '[' && ch != ']') || (tmp == '(' && ch != ')'))
                return 0;
        }
    }
    return isEmpty(&s);
}
 
int main()
{
    char str[]="[(){}[(){}]]";
    isRightBraket(str) ? puts("True") : puts("False");
    return 0;
}
cs


>> 28-29 : 여는 괄호에 대한 짝이 안맞으면 0을 리턴.

>> 30 : 검사가 끝나면 스택은 비워있어야 하므로..!!


>> 26번 라인잉 추가되었다. 이 코드가 없으면 닫는 괄호로 먼저 시작하는 코드들에 대해 에러가 발생한다. (수정:180514)



2. 중위식을 후위식으로 만드는 함수 (http://boj.kr/1918)


- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.


- 규칙

>> 피연산자를 만나면 그대로 출력

>> 연산자를 만나면 스택에 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
#include <stdio.h>
#define MAX 100
 
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, char data)
{
    s->s[++(s->top)] = data;
}
 
char peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int getPriority(char op)
{
    switch(op) {
        case '*': case '/': return 10;
        case '+': case '-': return 1;
    }
    return 0;
}
 
void infixToPostfix(char *t)
{
    Stack s;
    init(&s);
 
    for(int i=0; t[i]; i++) {
        char ch = t[i];
        if('A' <= ch && ch <= 'Z') printf("%c", ch);
        else {
            if(ch == '(') push(&s, ch);
            else if(ch == ')') {
                char op = peek(&s);
                while(op != '(') {
                    printf("%c", op);
                    pop(&s);
                    op = peek(&s);
                }
                pop(&s);
            }
            else {
                int curP = getPriority(ch);
                while(curP <= getPriority(peek(&s))) {
                    printf("%c", peek(&s)); 
                    pop(&s);
                }
                push(&s, ch);
            }
        }
    }
    while(!isEmpty(&s)) {
        printf("%c", peek(&s));
        pop(&s);
    }
}
 
int main()
{
    char s[100];
    scanf("%s", s);
    infixToPostfix(s);
    puts("");
    return 0;
}
 
cs


>> 이전 튜터링(스택) 때 서술한 알고리즘을 그대로 구현한 코드다

>> A+(B*C)*D*E+F   —>    ABC*D*E*+F+  이렇게 결과가 나온다.



3. 중위식을 후위식으로 만든 후 그 후위식을 계산하는 함수


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
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
 
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, char data)
{
    s->s[++(s->top)] = data;
}
 
char peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int getPriority(char op)
{
    switch(op) {
        case '*': case '/': return 10;
        case '+': case '-': return 1;
    }
    return 0;
}
 
char* infixToPostfix(char *t)
{
    char *res = (char*)malloc(sizeof(char)*100);
    int idx=0;
 
    Stack s;
    init(&s);
 
    for(int i=0; t[i]; i++) {
        char ch = t[i];
        if('0' <= ch && ch <= '9') { res[idx++]=ch; printf("%c", ch); }
        else {
            if(ch == '(') push(&s, ch);
            else if(ch == ')') {
                char op = peek(&s);
                while(op != '(') {
                    printf("%c", op);
                    res[idx++]=op;
                    pop(&s);
                    op = peek(&s);
                }
                pop(&s);
            }
            else {
                int curP = getPriority(ch);
                while(curP <= getPriority(peek(&s))) {
                    printf("%c", peek(&s)); 
                    res[idx++] = peek(&s);
                    pop(&s);
                }
                push(&s, ch);
            }
        }
    }
    while(!isEmpty(&s)) {
        printf("%c", peek(&s));
        res[idx++] = peek(&s);
        pop(&s);
    }
    res[idx] = 0;
    return res;
}
 
int exp(const char *eq)
{
    int i;
    Stack s;
    init(&s);
 
    for(i=0; eq[i]; i++) {
        if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0');
        else {
            int op2 = peek(&s); pop(&s);
            int op1 = peek(&s); pop(&s);
            switch(eq[i]) {
                case '+': push(&s, op1+op2); break;
                case '-': push(&s, op1-op2); break;
                case '*': push(&s, op1*op2); break;
                case '/': push(&s, op1/op2); break;
            }
        }
    }
    return peek(&s);
}
 
int main()
{
    char s[100], *t;
    scanf("%s", s);
    printf("%s = ", s);
    t=infixToPostfix(s);
    printf(" = %d\n", exp(t));
    free(t);
 
    return 0;
}
 
cs


>> input : 8/2-3+3*2

>> output : 8/2-3+3*2 = 82/3-32*+ = 7


>> infixToPostfix() 에서 출력을 할 때마다 해당 문자를 배열에 저장하고,

     이전에 구현해놓은 exp() 를 그대로 사용하면 된다..

     여기서 후위식을 저장할 배열을 왜 동적할당을 했는지 생각해보자..!! (지역변수 관련)



4. 미로탐색

...

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 트리(Tree)  (0) 2018.03.02
180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06

180220 튜터링 - 스택

Tutoring/17-2 Data Structure (Winter)2018. 2. 21. 22:57

< 숙제 Review >


- 3자리마다 콤마 찍기 (재귀)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
void comma(int n)
{
    int tmp = n/1000;
    if(tmp > 0) {
        comma(tmp);
        printf(",%03d", n%1000);
    }
    else {
        printf("%d", n);
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    comma(n);
 
    return 0;
}
cs



- %03d : 3자리 확보, 빈자리는 0으로..!!




< Tutoring >


- 스택의 정의 : 나중에 들어온 데이터가 먼저 꺼내진다. 

>> 그냥 프링글스 ㅎㅎ


- 스택의 ADT 및 구현하기


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
#include <stdio.h>
#define MAX 100
typedef struct stack {
    int s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, int data)
{
    s->s[++(s->top)] = data;
}
 
int peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int main()
{
    Stack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    isFull(&s) ? puts("Full") : puts("Not Full");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    return 0;
}
 
cs


>> 실행결과


Empty

Not Full

7

5

3

1

Empty



- 연결리스트를 이용한 구현 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
   char data;
   struct node * next;
} Node;
 
typedef struct listStack {
   Node * top;
} ListStack;
 
void init(ListStack * list) {
   list->top = NULL;
}
 
int isEmpty(ListStack * list) {
   return list->top == NULL;
}
 
int peek(ListStack * list) {
   if(isEmpty(list)) {
      printf("빈 스택임");
      return -111111;
   }
   
   return (list->top)->data;
}
 
void push(ListStack * list, int data) {
   Node * tmp = (Node*) malloc(sizeof(Node));
   tmp->data = data;
   tmp->next = list->top;
   list->top = tmp;
}
 
void pop(ListStack * list) {
   Node *tmp = list->top;
   list->top = tmp->next;
   free(tmp);
}
 
int main()
{
    ListStack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    return 0; 
}
 
cs


>>  



- 스택의 응용


1) 괄호검사 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ) // 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void RightBracket(const char * str) {
   ListStack l1;
   init(&l1);
   
   int i; for(i=0; str[i]; i++) {
      if(str[i] == '(') push(&l1, '(');
      if(str[i] == ')') {
         if(!isEmpty(&l1)) pop(&l1);
         else {
            printf("NO\n");
            return;
         }
      }
   }
   
   if(isEmpty(&l1)) printf("YES\n");
   else printf("NO\n");
}
cs


>> 5 줄에서 for 문의 조건식을 보자. 

>> 문자열의 마지막은 널문자이다. 널문자의 아스키코드값은 0.

>> 0은 조건식에서 거짓이다.



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
int exp(const char *eq)
{
    int i;
    Stack s;
    init(&s);
 
    for(i=0; eq[i]; i++) {
        if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0');
        else {
            int op2 = peek(&s); pop(&s);
            int op1 = peek(&s); pop(&s);
            switch(eq[i]) {
            case '+': push(&s, op1+op2); break;
            case '-': push(&s, op1-op2); break;
            case '*': push(&s, op1*op2); break;
            case '/': push(&s, op1/op2); break;
            }
        }
    }
    return peek(&s);
}
 
int main()
{
    printf("%d\n", exp("234*+"));       // 14
    printf("%d\n", exp("82/3-32*+"));   // 7
    return 0;
}
 
cs


>> 10 : 오른쪽 피연산자가 먼저 꺼내짐에 주의.

>> 7 : 문자열의 끝은 널문자인데, 널문자의 아스키코드값은 0. 0은 조건식에서 거짓. 즉 널물자를 만나면 for 문을 탈출한다.

>> for 문의 조건식에 strlen(eq[i]) 라고 적는것은 안좋다.

     for 문의 경우 초기식 - (조건식, 바디, 증감식)의 반복 으로 이루어 지는데, 조건식을 확인할 때마다 strlen() 함수가 작동한다.

     O(n) 으로 해결할 것도 O(n^2) 이 되버리는 신기한(?) 일이 발생한다.



3) 중위식을 후위식으로 바꾸기.


- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.


- 규칙

>> 피연산자를 만나면 그대로 출력

>> 연산자를 만나면 스택에 push.

>> 스택의 맨 위 연산자의 우선순위가 새로 추가되는 연산자의 우선순위보다 높거나 같다면 꺼내서 출력

>> ( 가중치에 상관없이 스택에 쌓는다. 

>> ) 가 나오면 스택에서 ( 위에 쌓여 있는 모든 연산자를 출력. 그리고 ( 는 꺼내서 버린다.



< 소스코드 >


>> 숙제.





< 숙제 >

- 복습 잘하기

- 올바른 괄호 문자열인지 판단하는 함수( "(", "{", "[" : 세 종류의 괄호 사용)

- 중위식을 후위식으로 만드는 코드.(http://boj.kr/1918)

- 중위식을 후위식으로 만든 다음 그 후위식을 계산하는 코드

- 큐 예습해오기.


'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06
180130 튜터링 - 재귀함수 만들기, 분석하기  (0) 2018.02.06

180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트

Tutoring/17-2 Data Structure (Winter)2018. 2. 14. 00:15

< 숙제 review >


1) 팰린드롬인지 판단한는 함수 재귀함수로 구현하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <string.h>
 
int isP(char str[], int s, int e)
{
    if(s >= e) return 1;
    return str[s]==str[e] ? isP(str, s+1, e-1) : 0;
}
 
int main()
{
    char str[100];
    scanf("%s", str);
    isP(str, 0, strlen(str)-1) ? puts("True") : puts("False");
    return 0;
}
 
cs


>> 첫번째 인덱스와 마지막 인덱스의 문자가 같을때, 그 안의 문자열이 팰린드롬이면 팰린드롬이다.



2) 리스트의 내용을 모두 출력하는 함수 만들기


1
2
3
4
5
6
7
8
void printList(List *list)
{
    Node *p = list->head;
    while(p != NULL) {
        printf("%d\n", p->data);
        p = p->next;
    }
}
cs




< Tutoring >


< 연결리스트의 전체노드 삭제 >


1
2
3
4
5
6
7
8
9
10
void deleteList(List *list)
{
    Node *p = list->head;
    while(p != NULL) {
        Node *tmp = p;
        p = p->next;
        free(tmp);
    }
    init(list);
}
cs


>> 위 예제의 응용에 불과하다고 생각함.

>> 동적할당으로 생성된 변수는 free() 를 통해 해제를 시킬 수 있다.

>> 9번은 다 지우고 난 다음 초기화를 다시 해주는 역할 정도..



< 연결리스트에서 특정 노드의 삭제 >


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void deleteNode(List *list, int pos)
{
    int k = 1;
    Node *prev, *cur = list->head;
    if(pos == 1) {
        list->head = list->head->next;
        free(cur);
        return ;
    }
    
    while(k < pos) {
        k++;
        prev = cur;
        cur = cur->next;
    }
    prev->next = cur->next;
    free(cur);
}
cs


>> 11~14 에서 첫번째 노드가 1번 노드라고 할 때, k번째 노드는 cur 가 가리키게 된다.

>> 하지만 위의 코드는 pos 의 값이 노드의 갯수보다 큰 값이 들어오면 에러가 발생한다.


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
void deleteNode2(List *list, int pos)
{
    int k = 1;
    Node *prev, *cur = list->head;
 
    if(cur == NULL)
        return ;
 
    if(pos == 1) {
        list->head = list->head->next;
        free(cur);
        return ;
    }
    
    while(cur != NULL && k < pos) {
        k++;
        prev = cur;
        cur = cur->next;
    }
 
    if(cur == NULL) {
        puts("Position does not exist.");
        return ;
    }
 
    prev->next = cur->next;
    free(cur);
}
cs



>> 어떤 부분들이 바뀌었는지 비교해봐 얘들아.. ㅎㅎ

>> 그외 List 주머니에 사이즈 관련 변수 하나 만들어서 노드의 개수를 카운트 해나가면서

     pos 값이 그 사이즈 안에 있는 값인지 체크하는 방법으로 해도 되고, 상황에 맞게 하면 될듯.!!



< 원형연결리스트의 삽입 (앞에) >


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
void CircularListAdd(List *list, int data)
{
    Node *p, *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
 
    if(list->head == NULL) {
        list->head = newNode;
        newNode->next = newNode;
        return ;
    }
 
    p = list->head;
    while(p->next != list->head)
        p = p->next;
 
    p->next = newNode;
    newNode->next = list->head;
    //list->head = newNode;
}
 
void printCircularList(List *list)
{
    Node *cur = list->head;
 
    if(cur == NULL) return ;
 
    do {
        printf("%d\n", cur->data);
        cur = cur->next;
    } while(cur != list->head);
}
 
int main()
{
    List list;
    init(&list);
    
    CircularListAdd(&list, 1);
    CircularListAdd(&list, 3);
    CircularListAdd(&list, 7);
    CircularListAdd(&list, 5);
 
    printCircularList(&list);    
 
    return 0;
}
cs


>> 18 : 원형 연결리스트의 데이터를 삽입하는 함수.

>> 38 : 원형 연결리스트의 데이터를 출력하는 함수


>> 60 의 결과는 1, 3, 7, 5

>> 35 의 주석을 해제했을 때, 60의 결과는 5, 7, 3, 1

>> 즉 35가 없으면 뒤로 삽입, 있으면 앞으로 삽입을 하는 결과가 만들어진다.


>> 다만 위의 코드에서는 삽입을 할때, 항상 맨 마지막 노드를 찾아야 하는 번거로움(?)이 있다.

     하지만 헤드포인터를 테일이라고 생각하고 코드를 작성하면 그럴필요가 없어진다..!!


1
2
3
4
5
6
7
8
9
10
11
12
13
void CircularListAdd2(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    if(list->head == NULL) {
        list->head = newNode;
        newNode->next = newNode;
        return ;
    }
    newNode->next = list->head->next;
    list->head->next = newNode;
    //list->head = newNode;
}
cs


>> head 를 tail 이라고 생각하면 된다.

>> 12 가 없으면 앞으로 삽입, 12가 있으면 뒤로 삽입하는 코드가 된다.



< 원형연결리스트의 노드들 중 홀수의 갯수 세기 >


- printCircularList() 에서 홀수인지만 판단한는 조건만 추가하고 계산 후 그 값을 리턴하면 된다.

- 그러니 우리는 if(cur->data & 1) 이라는 표현에 대해 알아보자.


>> & 는 비트 연산자로 각 비트별 AND 연산을 수행한다.

>> 참고로 모든 홀수의  마지막 비트(2^0)은 항상 1 이다.

     모든 짝수의 마지막 비트는 항상 0 이다.

>> 1 은 8비트 기준 00000001 이다.

>> 그러므로 1과 & 연산을 하면, 마지막 비트를 제외한 비트는 1이든 0이든 AND 연산의 결과는

    0이 나온다. 그렇기 때문에 홀수와 1에 대해 &(AND) 연산을 하면 항상 1이 나온다.

>> 조건식에서 1은 참을 의미한다..



cf) -1 은 비트로 표현하면 1로만 구성이 된다. 8비트라면 11111111 이 된다.

>> 1을 더하면 0이 되므로 증명 끝..

>> -2는 -1에서 1을 빼면 된다. 그러므로 -2는 8비트기준 11111110 이 된다.

>> -3은 -1에서 2를 빼면 된다. 그러므로 -3은 8비트 기준 11111101 이 된다.


>> 작은 수들은 굳이 2의 보수 취하지 않고도 이런식으로 구할 수 있다.



< 양방향 연결리스트의 삽입 >


- 우리가 지금까지 했던 연결리스트는 한방향으로만 연결이 되어 있다.

  하지만, 양방향 연결리스트는 말 그대로 양방향으로 연결이 되어 있다. 그러므로 prev 같은 노드 

  포인터가 필요없어진다.

- 노드에 대한 디자인도 새로 해야한다.


1
2
3
4
5
typedef struct node {
    int data;
    struct node *next;
    struct node *prev;
} Node;
cs


>> 4 : 이전 노드를 가리키기 위한 포인터가 추가되었다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insertNode(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
 
    if(list->head == NULL)
        list->head = newNode;
    else {
        newNode->next = list->head;
        list->head->prev = newNode;
        list->head = newNode;
    }
}
cs


>> 앞으로 삽입하는 코드. 

>> 6, 12번 줄이 추가가 된다.



< 더미노드를 이용한 양방향 연결리스트의 삽입 >


- 더미노드를 사용하면 list->head 가 가리키는 노드가 바뀌는 것에 대한 염려를 안해도 된다.

- 더미노드를 사용하면 init() 함수를 수정해주어야 한다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void init(List *list)
{
    list->head = (Node*)malloc(sizeof(Node));;
    list->head->prev = NULL;
    list->head->next = NULL;
}
 
void insertNode(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
 
    newNode->next = list->head->next;
    list->head->next = newNode;
    newNode->prev = list->head;
}
cs


>> 그리고 삽입코드는 위와 같이 쓸 수 있다.




< 숙제 >

- 복습잘하기

- 이중연결리스트에서 position 값이 주어졌을 때, 해당 위치에 노드를 삭제하는 함수 만들기


- 양의 정수를 입력 받았을 때, 3자리 마다 , 를 찍어서 출력해주는 함수(재귀로)

   input : 1000000 >> output : 1,000,000


- 스택, 중위식을 후위식으로 표기하는 방법, 후위식을 계산하는 방법 예습해오기


'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180206 튜터링 - 연결리스트  (0) 2018.02.06
180130 튜터링 - 재귀함수 만들기, 분석하기  (0) 2018.02.06

180206 튜터링 - 연결리스트

Tutoring/17-2 Data Structure (Winter)2018. 2. 6. 23:29

< 재귀함수 숙제 review >


- 1부터 n까지의 숫자중 홀수/짝수의 합 구하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
int oddSum(int n)
{
    if(n < 1) return 0;
    if(n%2 == 0) n--;
    return n + oddSum(n-2);
}
 
int evenSum(int n)
{
    if(n < 1) return 0;
    if(n%2 == 1) n--;
    return n + evenSum(n-2);
}
 
int main()
{
    int n = 100;
    printf("%d\n", oddSum(n)); 
    printf("%d\n", evenSum(n)); 
    return 0;
}
cs


>> 6번째 줄을 if(!(n%2)) 로 쓸 수도 있다.

>> 13번째 줄은 if(n&1) 로 쓸 수 있다.



- 배열의 요소들 중에서 최대값 구하기.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int f(int arr[], int n)
{
    int k;
    if(n == 0) return arr[0];
    k = f(arr, n-1);
    return k > arr[n] ? k : arr[n];    
}
 
int main()
{
    int arr[] = {10, 2, 30, 11, 50, 33};
 
    printf("%d\n", f(arr, 5));
    return 0;
}
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
#include <stdio.h>
 
int max;
 
int f2(int arr[], int n)
{
    int k;
    if(n == 1) {
        max = arr[n] > arr[n-1] ? arr[n] : arr[n-1];
        return arr[n] > arr[n-1] ? arr[n-1] : arr[n];
    }
    k = f2(arr, n-1);
    
    if(arr[n] < k) return k;
    if(arr[n] > max) { int t=max; max=arr[n]; return t; }
    return arr[n];
}
 
int main()
{
    int arr[] = {50, 10, 2, 30, 11, 33};
 
    printf("%d\n", f2(arr, 5));
    return 0;
}
cs


>> n 은 마지막 인덱스



< 연결리스트 >




- 노드 디자인 하기


1
2
3
4
typedef struct node {
    int data;
    struct node *next;
} Node;
cs


>> 자기참조 구조체

>> typedef 의 역할 // ex) typedef int INT;

>> 구조체는 자료형이다. 사용자 정의 자료형. 즉, 우리가 만든 자료형이다.



- List 주머니(?) 디자인 하기.


1
2
3
typedef struct list {
    Node *head;
} List;
cs



- 리스트 생성 후 초기화 하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
 
typedef struct node {
    int data;
    struct node *next;
} Node;
 
typedef struct list {
    Node *head;
} List;
 
void init(List *list)
{
    list->head = NULL;
}
 
int main()
{
    List list;
    init(&list);
 
    return 0;
}
cs


>> 19 : List 타입의 list 변수 생성

>> 20 : list 를 초기화 하는 코드. C++에서 생성자를 수동으로 실행시킨다고 생각하면 될 것 같다.



- 데이터 삽입하기.


1
2
3
4
5
6
7
8
9
10
11
12
13
void insertNode(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
 
    if(list->head == NULL)
        list->head = newNode;
    else {
        newNode->next = list->head;
        list->head = newNode;
    }
}
cs

 

>> 3 : 동적할당으로 #include <stdlib.h> 헤더파일이 필요하며, 

   결과 값으로 이름없는 변수의 주소값을 리턴한다. 그리고 그 주소를 newNode 에 저장.


>> 3, 5, 1 순으로 삽입을 하면 (head)->(1)->(5)->(1)->NULL 모양의 리스트가 만들어 진다.

     즉, 앞쪽으로 데이터가 삽입이 된다.

     (그림은 머릿속으로.....)


>> newNode->data : newNode가 가리키는 변수의 멤버 data (고요속의 외침..ㅎㅎ)


>> 아래와 같이 분기를 하지 않아도 될 것 같다.


1
2
3
4
5
6
7
void insertNode(List *list, int data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = list->head;
    list->head = newNode;
}
cs


>> 검증은 못해봄. 누가 테스트 해보고 결과좀 알려줘. ㅎ



- 데이터 뒤로 삽입하기. 

1) 리스트 주머니 수정하지 않고 해보기.

2) 리스트 주머니를 수정해서 해보기.



1) 의 경우


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertNodeBack(List *list, int data)
{
    Node *prev, *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
 
    if(list->head == NULL) {
        list->head = newNode;
    }
    else {
        prev = list->head;
        while(prev->next != NULL)
            prev = prev->next;
        prev->next = newNode;
    }
}
cs


>> 12-13 : prev 를 통해 맨 마지막 노드를 찾는 코드이다. 

>> 14 : 맨 마지막 노드를 찾았으면, 거기에 새 노드를 연결하면 될 듯.




### 자료구조 공부할 때, 특히 포인터등이 헷갈릴때는 그림을 그려가면서 해봐 얘들아 ㅎㅎ



### 숙  제 ###


- 복습 잘하기.

- 어떤 문자열이 주어졌을 때, 해당 문자열이 팰린드롬(회문)인지 판단하는 함수 재귀함수로 만들기

- 리스트의 내용을 모두 출력하는 함수 만들기

- 양방향 연결4리스트, 환형 연결리스트 예습해오기.

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180130 튜터링 - 재귀함수 만들기, 분석하기  (0) 2018.02.06

180130 튜터링 - 재귀함수 만들기, 분석하기

Tutoring/17-2 Data Structure (Winter)2018. 2. 6. 23:23

< 180130 튜터링 >

 

1 재귀함수 만들기.

>> 함수를 잘 정의하고, 그 정의를 그대로 활용하기

>> 어떻게 쪼갤지 생각하기..

>> 언제까지??(재귀의 종료, 탈출조건)

>> 점화식을 알고 있다면 그대로 표현하기.

 

- 팩토리얼 계산하는 함수

- 1부터 n까지의 합 구하는 함수

- 1 부터 n 까지 출력하는 함수

- n 부터 1까지 거꾸로 출력하는 함수

- a 의 n승 (파워함수)을 구하는 함수

- 배열 요소들의 합 재귀함수로 구하기.

 

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
#include <stdio.h>
 
int sum(int n)
{
    if(n < 1) return 0;
    return n+sum(n-1);
}
 
int evenSum(int n)
{
    if(n < 1) return 0;
    if(n%2 != 0) n--;
    return n+evenSum(n-2);
}
 
void print1(int n)
{
    if(n < 1) return ;
    print1(n-1);
    printf("%d\n", n);
}
 
void print2(int n)
{
    if(n < 1) return ;
    printf("%d\n", n);
    print2(n-1);
}
 
 
int main()
{
    int n;
    scanf("%d", &n);
 
    printf("%d\n", sum(n));
    printf("%d\n", evenSum(n));
    print1(n); // 1 to n
    puts("");
    print2(n); // n to 1
}
 
cs



2. 함수의 호출과정

- 하노이 타워 코드가 왜 그렇지 구현되어 있는지.

(이해 안되면, Hanoi(3, ‘A’, ‘B’, ‘C’); 손으로 써가면서 따라가봐 ㅎㅎㅎㅎ)

 

- 아래 세 함수의 결과는 같지만, 호출 순서가 어떻게 다른지 생각해보기

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void f(int n)
{
    if(n == 0) return ;
    f(n-1);
    f(n-1);
    printf(“*”);
}
 
void f(int n)
{
    if(n == 0) return ;
    f(n-1);
    printf(“*”);
    f(n-1);
}
 
void f(int n)
{
    if(n == 0) return ;
    printf(“*”);
    f(n-1);
    f(n-1);
}
cs



 

3. 동적 프로그래밍

- 피보나치 함수를 구해주는 함수에서 전달값이 크면 왜 느려지는지 생각해보기.

- 이를 해결하기 위한 방법 중 하나를 소개 했지만, 어려우면 넘어가도 됨.

  (메모이제이션)

 

### 숙제 ###

- 복습 잘 하기.

- 1부터 n 까지의 수 중 홀수(혹은 짝수)의 합 구하는 함수 구하기(재귀)

- 배열의 요소들 중 최대값(혹은 최소값) 재귀함수로 구하기.(재귀)

- 배열의 요소들 중 두번째 최대값 재귀함수로 구하기. (재귀)

(힌트가 필요하면 갠톡으로..)

- 연결리스트 개념 공부해오기

'Tutoring > 17-2 Data Structure (Winter)' 카테고리의 다른 글

180301 튜터링 - 큐(Queue)  (0) 2018.03.01
180301 튜터링 - 스택의 응용 (수정:180514)  (0) 2018.03.01
180220 튜터링 - 스택  (0) 2018.02.21
180213 튜터링 - 연결리스트, 양방향, 원형 연결리스트  (0) 2018.02.14
180206 튜터링 - 연결리스트  (0) 2018.02.06

티스토리툴바