'Tutoring' 카테고리의 글 목록

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
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
Colored by Color Scripter
cs

>> Min Heap 으로 구현.

>> 루트의 인덱스는 1로 두고 구현.

>> push() : n번째 노드는 완전이진트리 기준 n번째 위치를 cur로, cur의 부모 인덱스를 p로 두고 시작.

부모노드와 비교하여, 현재 노드값이 부모노드의 값보다 작으면, 부모노드의 값을 현재노드 위치로 당긴다. (35라인)

보통 스왑을 하지만, 나중에 자기 위치만 찾은다음 대입만 해주는 식으로 구현을 하였다.

부모의 인덱스가 0이라는 것은 더이상 부모가 없다는 뜻. 즉, 15라인은 부모가 존재하는데, 부모의 값보다 대상 데이터의 값이 작다면 이과정을 반복.

>> pop() : 팝은 맨 마지막 데이터를 루트에 두고 자기자리를 찾아가는 과정으로 생각하면 된다.

자기 자리를 찾아갈때는, 자식의 인덱스가 전체 사이트의 크기보다 작은지를 확인하면 된다.

자식의 인덱스가 사이즈보다 크다는 것은 더이상의 자식이 존재하지 않는다는 뜻.

그리고 자식이 존재하는데(child < size), 두개의 자식이 존재한다면(child+1 < size) 둘중 작은 값을 가진 자식과 교환을 해야한다.!!

>> 구현 아이디어는 윤성우의 열혈 자료구조 + 생능 출판사의 천인국 저자 책. 학교 교잰데 이름 기억안남;;

<문제풀이>

[1927] 최소 힙 : http://boj.kr/1927

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
/*** Min Heap ***/
/*** boj.kr/1927 ***/
 
#include <iostream>
using namespace std;
 
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    Priority_queue<int> pq;
    while(n--) {
        int k;
        cin >> k;
 
        if(k) pq.push(k);
        else {
            int ans;
            if(pq.empty()) ans = 0;
            else {
                ans = pq.top();
                pq.pop();
            }
            cout << ans << '\n';
        }
    }
}
 
Colored by Color Scripter
cs

[11286] 절대값 힙 : http://boj.kr/11286

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
#include <cstdio>
#include <vector>
#define MAXN    100000
 
using namespace std;
 
typedef pair<int, int> pii;
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && (heap[p].first > data.first || ((heap[p].first == data.first) && (heap[p].second > data.second)))) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size) {
                if(heap[child].first > heap[child+1].first) child++;
                else if(heap[child].first == heap[child+1].first) {
                    if(heap[child].second > heap[child+1].second) child++;
                }
            }
            if(heap[size].first > heap[child].first || ((heap[size].first==heap[child].first)&&(heap[size].second > heap[child].second))) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
 
};
 
int main()
{
    int n;
    scanf("%d", &n);
 
    Priority_queue<pii> pq;
    while(n--) {
        int k;
        scanf("%d", &k);
 
        if(k) {
            int tmp = k < 0 ? -k : k;
            pq.push(pii(tmp, k));
        }
        else {
            int ans;
            if(pq.empty()) ans=0; 
            else { ans = pq.top().second; pq.pop(); }
            printf("%d\n", ans);
        }
    }
}
 
Colored by Color Scripter
cs

>> 절대값이 같으면 원래값이 작은 순으로 MinHeap 구현

>> 힙 구현한것을 바꾸지 않고 하는 방법 (referenced by kyujeong)

#include <iostream>
using namespace std;
 
#define MAXN    100000
 
template<typename T>
struct Priority_queue {
    T heap[MAXN];
    int size;
    
    Priority_queue() : size(0) {}
    
    void push(T data) {
        int cur = ++size;
        int p = cur>>1;
 
        /*** Min Heap ***/
        while(p != 0 && heap[p] > data) {
            heap[cur] = heap[p];
            cur = p;
            p >>= 1;
        }
        heap[cur] = data;
    }
 
    bool empty() { return size == 0; }
    
    T top() { return heap[1]; }
 
    void pop() {
        if(size == 0) return ;
 
        int cur = 1, child = cur<<1;
 
        while(child < size) {
            if(child+1 < size && heap[child] > heap[child+1]) child|=1;
            if(heap[size] > heap[child]) {
               heap[cur] = heap[child];
               cur = child;
               child <<= 1;
            }
            else break;
        }
        heap[cur] = heap[size--];
    }
};
 
int main()
{
    cin.tie(NULL);
    std::ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    Priority_queue<double> pq;
    while(n--) {
        double k;
        cin >> k;
 
        if(k > 0) pq.push(k+0.1);
        else if(k < 0) pq.push(-k);
        else {
            int ans;
            double top;
            if(pq.empty()) ans = 0;
            else {
                top = pq.top();
                if(top == (int)top) ans = -(int)top;
                else ans = (int)top;
                pq.pop();
            }
            cout << ans << '\n';
        }
    }
}
 

Colored by Color Scripter

<멘토님 코드>

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
#include <cstdio>
using namespace std;
const int MAXN = 1e5 + 6;
 
template<typename T>
void swap(T *a, T *b) {
   T tmp = *a;
   *a = *b;
   *b = tmp;
}
 
template<typename T>
struct priority_queue {
   T arr[MAXN];
   int idx;
 
   priority_queue() :idx (0) {}
 
   bool empty() { return idx == 0; }
 
   int size() { return idx; }
 
   T top() { return arr[0]; }
 
   void push(T const &data) {
      arr[idx++] = data;      
      int curr = idx - 1;
      while (1) {
         if (curr == 0) break;
         int par = (curr - 1) / 2;
         if (arr[par] > arr[curr]) swap(&arr[par], &arr[curr]);
         curr = par;
      }
   }
 
   void pop() {
      arr[0] = arr[--idx];
      int curr = 0, next;
      while (curr * 2 + 1 < idx) {
         next = curr;
         if (arr[next] > arr[curr * 2 + 1]) next = curr * 2 + 1;
         if (curr * 2 + 2 < idx && arr[next] > arr[curr * 2 + 2]) next = curr * 2 + 2;
         if (next == curr) break;
         swap(&arr[curr], &arr[next]);
         curr = next;
      }
   }
};
 
int main() {
 
   priority_queue<int> pq;
   int n;
   scanf("%d", &n);
 
   for (int i = 0,d ; i < n; i++) {
      scanf("%d", &d);
      if (d == 0) {
         if (pq.empty()) printf("0\n");
         else printf("%d\n", pq.top()), pq.pop();
      }
      else pq.push(d);
   }
   return 0;
}
Colored by Color Scripter
cs

>> 종만북을 많이 참고한 코드라고 한다.

Week 1 - DP1

Tutoring/PS2018. 6. 26. 15:43

뷰어
댓글로
이전글
다음글

<180625>

### DP Basic ###

1) [11051] 이항계수2 : http://boj.kr/11051

combi(n, r) : nCr 을 구하는 함수. nCr = n-1Cr + n-1Cr-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
#include <stdio.h>
 
const int MOD=10007;
 
int d[1001][1001];
 
int combi(int n, int r)
{
    int *ret = &d[n][r];
    if(r == 0 || r == n) return 1;
    if(*ret != -1) return *ret;
 
    return *ret = (combi(n-1, r-1)+combi(n-1, r))%MOD;
}
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            d[i][j] = -1;
    printf("%d\n", combi(n, k));
    return 0;
}
Colored by Color Scripter
cs

2) [11055] 가장 큰 증가하는 부분 수열 : http://boj.kr/11055

d[i] : i ~ (n-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
#include <stdio.h>
 
int n;
int a[1001], d[1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lis(int s)
{
    int *ret = &d[s];
    if(s == n-1) return a[s];
    if(*ret) return *ret;
 
    *ret = a[s];
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i])
            *ret = max(*ret, a[s]+lis(i));
    }
    return *ret;
}
 
int main()
{
    int ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    for(int i=0; i<n; i++)
        ans = max(ans, lis(i));
    printf("%d\n", ans); 
    return 0;
}
 
Colored by Color Scripter
cs

3) [11048] 이동하기 : http://boj.kr/11048

d[i][j] : (i,j) 에서 이동해서 가져올 수 있는 사탕 갯수의 최대값

<소스코드>

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
#include <stdio.h>
 
int g[1001][1001];
int d[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int move(int r, int c)
{
    int *ret = &d[r][c];
    if(r <= 0 || c <= 0) return 0;
    if(*ret != -1) return *ret;
    
    *ret = move(r-1, c)+g[r][c];
    return *ret = max(*ret, move(r, c-1)+g[r][c]);
}
 
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = -1;
        }
    }
 
    printf("%d\n", move(n, m));
    return 0;
}
 
Colored by Color Scripter
cs

4) [11066] 파일합치기 : http://boj.kr/11066

d[i][j] : i~j번째 까지의 파일을 합치는 데 드는 최소 비용

<소스코드>

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
#include <stdio.h>
 
int n, a[501];
int d[501][501];
int pSum[501];
 
int min(int a, int b)
{
    return a < b ? a : b;
}
 
int file(int s, int e)
{
    int *ret = &d[s][e];
    if(s == e) return 0;
    if(*ret != -1) return *ret;
 
    *ret = 0x7fffffff;
    for(int i=s; i<e; i++) 
        *ret = min(*ret, file(s, i)+file(i+1, e)); 
    return *ret = *ret + (pSum[e]-pSum[s-1]);
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            pSum[i] = 0;
        for(int i=1; i<=n; i++) {
            scanf("%d", a+i);
            pSum[i] += (pSum[i-1]+a[i]);
 
            for(int j=1; j<=n; j++) 
                d[i][j] = -1;
        }
        printf("%d\n", file(1, n));
    }
 
    return 0;
}
 
Colored by Color Scripter
cs

>> 누적합을 누적해나가야 한다.

>> pSum 을 초기화 안해서 뻣질 많이 함...ㅜㅜ

<180629>

1) [2410] 2의 멱수의 합 : http://boj.kr/2410

2) [2228] 구간 나누기 : http://boj.kr/2228

'Tutoring > PS' 카테고리의 다른 글

Week 7 - DFS+BFS (0)	2018.04.07
Week 6 - BFS (숨박꼭질) (0)	2018.03.30
Week 5 - BFS (0)	2018.03.24
Week 4 - BFS (0)	2018.03.11
Week3 - DFS (0)	2018.03.07

Week 8-2 : Binary Search Tree (종강) (추가:180814)

Tutoring/18-1 DS2018. 6. 8. 00:49

뷰어
댓글로
이전글
다음글

<180608>

<소스코드>

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
#include <cstdio>
 
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data) : data(data), left(0), right(0) {}
};
 
class bst {
private:
    Node *root;
 
public:
    bst() : root(0) {}
    
    void insert(int data) {
 
        if(!root) {
            root = new Node(data); 
            return ;
        }
 
        Node *p = 0;
        Node *cur = root;
        while(cur) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
        if(p->data < data) p->right = new Node(data);
        else p->left = new Node(data);
    }
 
    Node* getRoot() { return root; }
 
    void display(Node *root) {
        if(!root) return ; 
        display(root->left);
        printf("%d\n", root->data);
        display(root->right);
    }
 
    void remove(int data) {
        Node *p = 0;
        Node *cur = root;
        while(cur && cur->data != data) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
 
        if(!cur) return ;
 
        if(cur->left == NULL && cur->right == NULL) {
            if(p == NULL) root = NULL;
            else {
                if(p->left == cur) p->left = NULL;
                else p->right = NULL;
            }
        }
        else if(cur->left == NULL || cur->right == NULL) {
            Node *child = cur->left ? cur->left : cur->right;
 
            if(p == NULL) root = child; 
            else {
                if(p->left == cur) p->left = child;
                else p->right = child;
            }
        }
        else {
            Node *sp = cur;
            Node *sc = cur->right;
 
            while(sc->left != NULL) {
                sp = sc;
                sc = sc->left;
            }
            
            if(sp->left == sc) {
                sp->left = sc->right;     
            }
            else
                sp->right = sc->right;
 
            cur->data = sc->data;
            cur = sc;
        }
 
        delete cur;
    }
};
 
int main()
{
    bst *t = new bst();
    t->insert(5);
    t->insert(1);
    t->insert(3);
    t->insert(2);
    t->insert(10);
    t->insert(9);
    t->insert(7);
    t->insert(8);
    t->display(t->getRoot()); puts("");
    t->remove(2);
    t->display(t->getRoot()); puts("");
    t->remove(1);
    t->display(t->getRoot()); puts("");
    t->remove(9);
    t->display(t->getRoot()); puts("");
    return 0;
}
 
Colored by Color Scripter
cs

1) 데이터의 삽입 과정

18 7 26 31 3 12 9 27

2) 데이터 찾기.

3) 데이터의 삽입

4) 데이터의 삭제

4-1) 타겟 노드가 단말노드인 경우

4-2) 타겟 노드가 자식을 하나만 가지고 있는 경우

4-3) 타겟 노드가 두개의 자식을 가지고 있는 경우

>> 타겟의 오른쪽 자식이 왼쪽 서브트리를 가진경우 or not

5) 데이터 탐색의 시간 복잡도

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-1 : Binary Tree 2 (0)	2018.06.05
Week 7-2 : Tree, Binary Tree (0)	2018.05.27
Week 7-1 : Stack, Queue by Linked List (0)	2018.05.19
Week 6 : Maze(with stack) / Circular Queue (0)	2018.05.16
Week 5-2 : infix to postfix, exp(postfix) (0)	2018.05.08

Week 12 - 종강

Tutoring/18-1 C Lang2018. 6. 6. 14:55

뷰어
댓글로
이전글
다음글

<180606>

1) 문자열의 길이 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
 
int main()
{
    char str[100];
    int len=0;
    int idx=0;
 
    scanf("%s", str);
 
    while(str[idx++] != 0) 
        len++;
 
    printf("%d\n", len);
    return 0;
}
cs

>> 문자열의 끝은 널문자이다..!!

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
#include <stdio.h>
 
int main()
{
    char str[100];
    int len=0;
    int idx=0;
 
    char str2[100];
 
    scanf("%s", str);
 
    while(str[idx++] != 0) 
        len++;
 
    printf("%d\n", len);
 
    idx = 0;
    for(int i=len-1; i>=0; i--)
        str2[idx++] = str[i];
    str2[idx] = 0;
 
    printf("%s\n", str2);
 
    return 0;
}
cs

>> 21 라인 : 널문자를 꼭 추가해줘야 한다. 널문자의 아스키코드 값은 0

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
#include <stdio.h>
 
int main()
{
    char str[100];
    char str2[100];
    char str3[100];
    int len=0, len2=0;
    int idx=0;
 
    scanf("%s", str);
    scanf("%s", str2);
 
    while(str[idx++] != 0) 
        len++;
 
    idx=0;
    while(str2[idx++] != 0) 
        len2++;
 
    idx=0;
    for(int i=0; i<len; i++)
        str3[i] = str[i];
 
    for(int i=0; i<len2; i++)
        str3[len++] = str2[i];
    str3[len] = 0;
 
    printf("%s\n", str3);
 
    return 0;
}
cs

>> 두 문자열의 길이를 구한 다음. 첫번째 문자의 널문자가 있는 위치부터 이어붙이면 된다.

>> 26 라인을 str3[len+i] 로 하고, 27라인을 str3[len+len2] = 0 으로 바꿔도 된다.

4) 배열과 포인터와의 관계

- 배열의 이름은 배열의 시작주소이며, 그 값을 바꿀 수 없는 상수형태의 포인터이다..!!

- 포인터(변수)는 변수이기 때문에 주소를 원할때마다 변경할 수 있다.

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 11 (0)	2018.05.30
Week 10 (0)	2018.05.23
Week 09 (0)	2018.05.16
Week 08 (0)	2018.05.09
Week 07 (0)	2018.05.05

Week 8-1 : Binary Tree 2

Tutoring/18-1 DS2018. 6. 5. 23:55

뷰어
댓글로
이전글
다음글

<180605>

0) 트리에서 노드의 갯수 구하기

1
2
3
4
5
int getNodeCnt(TreeNode *root)
{
    if(root == NULL) return 0;
    return 1+getNodeCnt(root->left)+getNodeCnt(root->right);
}
Colored by Color Scripter
cs

>> 트리의 노드의 갯수 = 자기 자신 + 왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수

1) 단말노드의 갯수 구하기

1
2
3
4
5
6
int getLeafNode(TreeNode *root)
{
    if(root == NULL) return 0;
    if(root->left == NULL && root->right == NULL) return 1;
    return getLeafNode(root->left) + getLeafNode(root->right);
}
Colored by Color Scripter
cs

>> 트리에서 단말노드의 갯수 = 왼쪽 서브트리에서의 단말노드의 갯수 + 오른쪽 서브트리에서의 단말노드의 갯수

>> 3 라인에서의 탈출조건이 필요하다. 이 코드가 없다면, root == NULL 인 경우 에러가 발생한다.

>> root 가 NULL 이라는 것은 root 가 가리키는 트리노드가 없다는 뜻이다. 그런데 root->left 가 의미하는 것은 root가 가리키는 변수의 멤버 left 가 된다.

가리키는 변수가 없는데, 가리키는 변수의 멤버를 찾는 셈이 된다.

2) 전위순회, 중위순회의 순서가 주어졌을 때, 후위순회의 순서 구하기

전위순회 순서 : 0 1 3 6 7 4 2 5 8 9

중위순회 순서 : 6 3 7 1 4 0 2 8 5 9

1. 전위순회의 경우, 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 맨 왼쪽에 있는 0 이 루트라는 사실을 알 수 있다.

2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.

그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며, 2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.

전위순회 순서 : [0] [1 3 6 7 4] [2 5 8 9]

중위순회 순서 : [6 3 7 1 4] [0] [2 8 5 9]

위와 같이 생각할 수 있다.

3. 이젠 왼쪽 서브트리에 대해 생각해보자.

전위순회 순서 : [1 3 6 7 4]

중위순회 순서 : [6 3 7 1 4]

위와 마찬가지로 전위 순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 순회를 한다. 그렇기 때문에 1 이 this 서브트리의 루트라는 사실을 알 수 있다.

4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.

그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.

5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 후위순회를 구하면 된다...!!

>> 프로그래밍 해보고 싶다면 도전!! (http://boj.kr/4256)

>> 내가 푼 코드 (https://github.com/YongHoonJJo/BOJ/blob/master/4256.cpp)

3) 중위순회, 후위순회의 순서가 주어졌을 때, 전위순회의 순서 구하기.

중위순회 순서 : 6 3 7 1 4 0 2 8 5 9

후위순회 순서 : 6 7 3 4 1 8 9 5 2 0

1. 후위순회의 경우, 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 순회를 한다. 그렇기 때문에 맨 오른쪽에 있는 0 이 루트라는 사실을 알 수 있다.

2. 중위순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.

그렇기 때문에 6 3 7 1 4 는 루트(0) 기준 왼쪽 서브트리에 있는 노드들이며, 2 8 5 9 는 루트(0) 기준 오른쪽 서브트리의 노드들이 된다.

3. 후위순회의 순서에서는 [6 7 3 4 1][8 9 5 2][0] 으로 생각할 수 있다.

여기서도 왼쪽 서브트리인 [6 7 3 4 1] 에 대해서 생각해보자. 후위순회는 왼쪽 서브트리에 대해서도 후위순회를 한다.

그렇기 때문에 1이 왼쪽 서브트리의 루트라는 것을 알 수 있다.

4. 중위 순회의 경우 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 순회를 한다.

그렇기 때문에 [[6 3 7][1][4]] 와 같이 생각할 수 있다. 1 기준 [6 3 7] 은 왼쪽 서브트리의 노드들, [4]는 오른쪽 서브트리의 노드가 된다.

5. 이 과정을 반복하면 원래의 트리를 복구할 수 있다. 이를 토대로 전위순회를 구하면 된다...!!

4) 트리의 삭제

1
2
3
4
5
6
7
int removeTree(TreeNode *root)
{
    if(root == NULL) return ;
    removeTree(root->left);
    removeTree(root->right);
    free(root);
}
cs

>> 전위순회를 하면 왼쪽 서브트리와 오른쪽 서브트리의 루트를 찾아갈 수 없다.

>> 중위순회를 해도 오른쪽 서브트리의 루트를 찾아갈 수 없게 된다.

>> 그래서 후위순회로 삭제를 진행해야 한다.

5) 트리에서 데이터의 값이 홀수인 노드의 갯수를 구하기

1
2
3
4
5
6
7
\int getOddNode(TreeNode *root)
{
    int cnt=0;
    if(root == NULL) return 0;
    if(root->data & 1) cnt++;
    return cnt + getOddNode(root->left) + getOddNode(root->right);
}
Colored by Color Scripter
cs

>> 트리에서 테이터의 값이 홀수인 노드의 갯수 = 자신(1 or 0) + 왼쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수 + 오른쪽 서브트리에서 테이터의 값이 홀수인 노드의 갯수

6) 디렉토리 용량 구하기.

>> 왼쪽 서브트리의 디렉토리의 용량 + 오른쪽 서브트리의 디렉토리의 용량 + 자기 자신의 용량

7) 수식트리

>> 단말노드에 피연산자가 들어있고, 그 외 노드에는 연산자가 들어있다.

>> 후위순회로 계산할 수 있다. 왼쪽 서브트리에서 계산한 결과와 오른쪽 서브트리에서 계산한 결과를 루트에 있는 연산자에 의한 연산을 하면 된다.

8) 레벨순회

- 큐 라는 자료구조를 사용하며, 나중에 배울 그래프에서의 너비우선탐색(BFS) 알고리즘과 완전히 동일하다.

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

(typedef element int 였다면 int를 TreeNode* 로 바꾸면 됬을텐데.. typedef element int 를 쓰는 이유를 다시한번 되새겨보자..!!)

- 알고리즘은 다음과 같다.

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

2) 큐가 비어 있지 않다면,

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

4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다(노드가 존재할 경우). 그리고 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
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
// Tree
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;
}
 
// 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;
    level(root);
}
 
Colored by Color Scripter
cs

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-2 : Binary Search Tree (종강) (추가:180814) (0)	2018.06.08
Week 7-2 : Tree, Binary Tree (0)	2018.05.27
Week 7-1 : Stack, Queue by Linked List (0)	2018.05.19
Week 6 : Maze(with stack) / Circular Queue (0)	2018.05.16
Week 5-2 : infix to postfix, exp(postfix) (0)	2018.05.08

Week 11

Tutoring/18-1 C Lang2018. 5. 30. 23:45

뷰어
댓글로
이전글
다음글

<180530>

1) 1 ~ 7 사이의 데이터를 10번 입력 받았을 때, 1~7사이의 값들이 각각 몇 번씩 입력받았는지 프로그래밍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main()
{
    int cnt[8]={0};
 
    for(int i=0; i<10; i++) {
        int k;
        scanf("%d", &k);
        cnt[k]++;
    }
 
    for(int i=1; i<8; i++) {
        printf("%d : ", i);
        for(int j=0; j<cnt[i]; j++)
            printf("*");
        printf("\n");
    }
 
    return 0;
}
Colored by Color Scripter
cs

>> 배열의 크기를 왜 8로 설정했는지 생각해보기.

>> 11번 라인이 끝났을 때, cnt[i] 에는 i 가 몇 번 입력이 들어왔는지에 대한 빈도수가 저장되어 있다..!!

>> input : 1 2 2 3 3 3 6 7 7 7

>> output

1 : *

2 : **

3 : ***

4 :

5 :

6 : *

7 : ***

2) -7 ~ 7 사이의 데이터를 10번 입력 받았을 때, 1~7사이의 값들이 각각 몇 번씩 입력받았는지 프로그래밍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
 
int main()
{
    int cnt[15]={0};
 
    for(int i=0; i<10; i++) {
        int k;
        scanf("%d", &k);
        cnt[k+7]++;
    }
 
    for(int i=0; i<15; i++) {
        printf("%d : ", i-7);
        for(int j=0; j<cnt[i]; j++)
            printf("*");
        printf("\n");
    }
 
    return 0;
}
Colored by Color Scripter
cs

>> 1번 문제와 무엇이 달라졌는지 살펴보자.

>> 배열의 인덱스는 0부터 사용이 가능하다. 즉 -7을 처리하기 위해 1번 문제와 같이 해서는 안된다.

>> 하지만, -7을 0으로 생각하고 다른 숫자들도 +7 한 값으로 생각을 하면 이를 해결할 수 있다.

>> 10번 라인과 14번 라인처럼 하면 된다.

>> 13번 라인에서 for문의 횟수는 [-7, 7] 까지이르로 총 15개의 정수에 대해 다루므로..

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int main()
{
    int lotto[46]={0};
    int cnt=0;
    srand(time(NULL));
 
    while(cnt < 6) {
        int k = rand()%45+1;
        if(lotto[k]==0) {
            lotto[k] = 1;
            cnt++;
        }
    }
 
    for(int i=1; i<=45; i++)
        if(lotto[i] == 1)
            printf("%d ", i);
    printf("\n");
    return 0;
}
cs

>> 랜덤함수는 스스로 학습해보기.

>> 1~ 45사이의 숫자를 랜덤으로 추출해야 한다. 임의의 값을 45로 나눈 나머지는 0~44사이의 값이 된다. 1을 더하면 1~45 사이의 값이 된다.

>> 11번를 while(cnt < 6) 으로 한 이유를 잘 생각해보자. for(int i=0; i<6; i++) 로 하면 딱 6번 값을 추출한다.

>> 하지만 이렇게 되면 중복된 숫자가 나온경우를 처리할 수 없다.

>> lotto[i] == 1 이라는 것은 i라는 숫자가 한번 나왔었다는 뜻. 그렇기 때문에 13번 라인의 조건식을 만족하지 않아, 카운트도 되지 않는다. 이로써 중복된 숫자를 해결할 수 있다.

>> 배열의 인덱스를 가지고 놀 줄 알아야 한다

4) 2차원 배열 개념

- 2차원 배열의 선언 : int arr[4][5]; // 8x10 크기의 사각형으로 된 방을 만들었다고 생각하면 된다. 8개의 층으로 된 건물(0에서 7층, 각 층마다 10개의 방)

- 참고로 배열의 이름은 배열의 시작주소 이다...!! (중요)

5) 전치행렬 (전치행렬 개념은 모르면 검색해보기..!!)

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
 
#include <stdio.h>
 
int main()
{
    int matrix[3][4];
    
    for(int i=0; i<3; i++) 
        for(int j=0; j<4; j++)
            scanf("%d", &matrix[i][j]);
 
    for(int i=0; i<3; i++) {
        for(int j=0; j<4; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    
    for(int i=0; i<4; i++) {
        for(int j=0; j<3; j++) {
            printf("%d ", matrix[j][i]);
        }
        printf("\n");
    }
 
    return 0;
}
Colored by Color Scripter
cs

>> 12-17 : 행(i)를 고정시키고 열 들을 한줄씩 출력

>> 19-24 : 열(i)를 고정시키고 행 들을 한줄씩 출력

>> 행렬의 합, 행렬의 곱 연산방법 확인 후 문제가 주어졌을 때, 어떻게 하면 될지 고민해보기..!

6) 3차원 배열 개념

7) 포인터 (변수)

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
 
int main()
{
    int n;
    int *p;
    n = 10;
    p = &n;
    *p = 20;
    printf("%d %d\n", n, *p);
}
cs

8) 주소 개념잡기

- (1)은 위의 코드에서 5번 라인.

- (2)은 위의 코드에서 6번 라인.

- (3)은 위의 코드에서 7번 라인.

- (4)은 위의 코드에서 8번 라인.

- (5)은 위의 코드에서 9번 라인을 수행했을때의 결과를 그림으로 표기한 것임.

>> 포인터(변수)도 포인터이다. 다면 변수의 주소를 저장하는 공간이고,

변수의 주소를 저장하고 있다는 것은 일반적으로 4, 5그림과 같이 화살표로 표기하며, p라는 포인터(변수)를 통해 변수 n에 접근을 할 수 있다.

>> 8번 라인에서 &는 피연산자인 변수의 주소를 알려주는 연산자 이다. 그렇다면 scanf() 에서 "", 다음 주소가 필요하다는 것을 생각해볼 수 있다.

>> 9번 라인에서 *는 참조 연산다. 포인터 변수 p가 가리키는 변수를 참조하여 값을 저장하거나 읽어올 수 있다.

9) 문자열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main()
{
    char str[]="Hello World!";
    printf("%s\n", str);
 
    str[6] = 'w';
    printf("%s\n", str);
 
    str[5] = '\0';
    printf("%s\n", str);
 
    return 0;
}
cs

>> 실행결과

Hello World!

Hello world!

Hello

>> 5 라인 : 배열의 크기를 지정하지 않고 초기화시 자동으로 초기화 한 만큼 크기가 설정된다.

>> 8 라인 : 문자열의 일부 문자를 수정했다. (변수형태의 문자열)

>> 문자열의 끝은 널문자이다. 11번 라인의 경우 중간에 널문자를 삽입했기 때문에 그 중간이 문자열의 끝으로 인식이 된 것이다

- 문자열의 입력

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int main()
{
    int n;
    char str[100];
 
    scanf("%d", &n);
    scanf("%s", str);
 
    printf("%d : %s\n", n, str);
    return 0;
}
 
Colored by Color Scripter
cs

- scanf() 를 통해 입력을 받을수 있으며, 공백을 포함하지 않는 문자열(일종의 한 단어)를 입력받을 수 있다.

>> 스캔에프 함수는 공백을 기준으로 입력을 받기 때문이다.

- 8번 라인 : & 연산자는 피연산자(변수)의 주소를 알려주는 연산자이다. 즉 저자리는 주소를 전달하는 자리이다.

- 9번 라인 : 여기서는 &가 없고 배열의 이름만 썼다. 배열의 이름은 배열의 시작주소 이기 때문이다.

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 12 - 종강 (0)	2018.06.06
Week 10 (0)	2018.05.23
Week 09 (0)	2018.05.16
Week 08 (0)	2018.05.09
Week 07 (0)	2018.05.05

Week 7-2 : Tree, Binary Tree

Tutoring/18-1 DS2018. 5. 27. 22:12

뷰어
댓글로
이전글
다음글

< 180517 >

1) 트리

- 계층구조를 표현하기 위한 비선형 자료구조. ex) 디렉토리

- 노드(형제, 부모, 자식, 루트, 단말)

- 서브트리의 개념 설명. 트리의 자식노드를 루트로 하는 트리.

- 레벨 : 루트노드 기준 노드까지의 거리. 루트의 레벨을 0 으로 두기도 하고, 1로 두기도 한다.

- 높이 : 최대레벨

- 트리의 예시 (그림 출처 : http://wwst.tistory.com/2)

- 트리의 종류 : 일반트리, 이진트리

2) 이진트리 (Binary Tree)

- 정의 : 각 노드별 자식노드가 두개 이하로 구성된 트리..(최대 두개의 자식노드)

- 성질 : 노드의 갯수 -1 = 간선의 수

- n 개의 노드로 최대 n 레벨을 만들수 있으며, 최소 ceil(log(n+1))의 레벨을 만들 수 있다. 로그의 밑은 2.

- 이진트리의 종류(일반 이진트리, 완전이진트리, 포화 이진트리)

- 포화이진트리 : 마지막 레벨까지 모든 레벨에 노드가 가득 차 있는 트리.

- 완전이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리.

- 일반이진트리 : 완전도 포화도 아닌 트리 (아래 그림에서 TreeA 는 일반 이진트리)

- 이진트리의 서브트리 (그림출처 : https://kks227.blog.me/221028710658)

>> 서브트리는 부모노드를 기준으로, 한 자식노드를 루트로 하는 트리

< 180529 >

- 이진 트리의 표현

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

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

- 트리의 순회 (그림출처 : https://kks227.blog.me/221028710658)

전위순회 : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 탐색

중위순회 : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 탐색

후위순회 : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 탐색

레벨순회 : 큐를 이용, 구현은 다음 시간에..!

>> 전위순회의 경우, 왼쪽 서브트리를 순회할때, 재귀적으로 왼쪽 서브트리의 루트를 기준으로 전위순회를 한다.

Preorder : ( 0 ) ( 1 3 6 7 4 ) ( 2 5 8 9 ) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리)

왼쪽 서브트리의 경우 1 3 6 7 4 인데 마찬가지로 (1) (3 6 7) (4) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.

위에서 왼쪽 서브트리는 3 6 7 인데, 마찬가지로 (3) (6) (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
#include <stdio.h>
#include <stdlib.h>
 
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);
   }
}
 
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("Tree의 높이 : %d\n", height(root));
   level(root);
}
 
Colored by Color Scripter
cs

>> 42 라인 : 트리에서 노드의 갯수는 왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 1(기준 트리의 루트노드) 이다.

>> preorderPrint() 라는 함수는 한 트리의 루트를 매개변수로 전달 받는다.

그리고 이 트리는 매개변수로 전달받은 루트를 기준으로 하는 트리에 대해 전위순회를 하는 함수이다.

전위순호는 루트를 방문하고, 왼쪽 서브트리에 대해 전위순회를 하고, 오른쪽 서브트리에 대해 전위순회를 진행하면 된다.

왼쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 왼쪽 서브트리의 루트를 매개변수로 전달하면 된다.

마찬가지로 오른쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 오른쪽 서브트리의 루트를 매개변수로 전달하면 된다.

>> 48 라인 : 트리의 높이는 max(왼쪽 서브트리의 높이, 오른쪽 서브트리의 높이)+1 이 된다.

>> 58 라인 : 트리의 삭제, 후위순회 방식으로 진행한다.

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 8-2 : Binary Search Tree (종강) (추가:180814) (0)	2018.06.08
Week 8-1 : Binary Tree 2 (0)	2018.06.05
Week 7-1 : Stack, Queue by Linked List (0)	2018.05.19
Week 6 : Maze(with stack) / Circular Queue (0)	2018.05.16
Week 5-2 : infix to postfix, exp(postfix) (0)	2018.05.08

How We Coding

<190116>

'Tutoring > 18-2 Final Tutoring' 카테고리의 다른 글

<190109>

< 190109 >

'Tutoring > 18-2 Final Tutoring' 카테고리의 다른 글

<190102>

< 190102 >

'Tutoring > 18-2 Final Tutoring' 카테고리의 다른 글

<180709> 우선순위 큐 (Priority Queue)

Week 1 - DP1

'Tutoring > PS' 카테고리의 다른 글

Week 8-2 : Binary Search Tree (종강) (추가:180814)

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 12 - 종강

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 8-1 : Binary Tree 2

'Tutoring > 18-1 DS' 카테고리의 다른 글

Week 11

'Tutoring > 18-1 C Lang' 카테고리의 다른 글

Week 7-2 : Tree, Binary Tree

'Tutoring > 18-1 DS' 카테고리의 다른 글

최근에 올라온 글

최근에 달린 댓글

공지사항

글 보관함

링크

티스토리툴바

« 2024/05 »
일	월	화	수	목	금	토
			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