정만수
75
2019-06-22 00:50:10 작성 2019-07-12 01:43:59 수정됨
4
1134

[포트폴리오] 괜히 C로 자료구조 구현해보려고 설쳤다가 해버렸습니다.


정보처리기사 실기 공부하다가 갑자기 자료구조에 꽂혀가지고

C언어로 구현 한 번 해보겠다고 설쳤다가 며칠을 고생해버렸습니다.

결국 구현은 어느정도 했어요 ㅜㅜ


https://github.com/pronist/DS

선배님들이 보기에는 어떤가요? 이진트리가 제일 힘들었어요..

0
0
  • 댓글 4

  • 비비
    366
    2019-06-22 02:05:24 작성 2019-06-22 02:10:39 수정됨

    1. 저도 학부생일 때, 자료구조 짜봤는데요.

    예전의 저보다 코드레벨이 훨씬 좋고, Git에 올려놓은 것도 좋네요.

    각 자료구조별 ADT도 좋은 것 같아요.

    2. Binary Tree라는 용어를 바꿔주세요.

    Binary Tree라는 자료구조가 존재하나요?

    Binary Tree라는 단어는 Binary Search Tree, AVL Tree, 2-3-4 Tree(Balanced Tree) 모두 해당됩니다.

    3. Binary Tree에서 Element 탐색할 때 소요되는 시간복잡도가 O(n)인가요?

    즉, Inorder인 Tree Traversal로 돌려서 검색하시는건가요?

    Binary Tree에서 Element를 Inorder로 검색하는 건,

    개인의 성취감일 뿐이고 자료구조로서의 의미는 없습니다.

    Binary Search Tree를 만들어서 최선의 경우에는 O(lgn)이 나오고, 최악의 경우 O(n)이 나와야합니다.

    0
  • sylee957
    30
    2019-06-22 02:27:51 작성 2019-06-22 02:37:58 수정됨

    훌륭하게 구현했군요.

    하지만 제가 해 본 경험으로는, C로 자료구조를 구현하면, 이미 토이 프로젝트라 속도 개선을 체감할 수 없는 건, 시각화에서 심심하면 재미가 없기 때문에

    Graphviz나, 파이썬의 NetworkX, 혹은 Sagemath나 Mathematica같은 CAS의 그래프 이론 패키지를 사용하는 것으로 나아가서, 아예 시각화 패키지들의 저수준 API로 중급 API를 클론 코딩하는 등등의 방식으로 공부를 했습니다.

    요즘 시대에는 컴퓨터 과학이나 계산수학이 너무 발전해서, 대학원 수준의 내용을 따라잡는데 수학적인 직관은 물론 기계 수준의 제어까지 챙기기는 불가능하지 않을까 봅니다.

    물론, 이런 것들을 이미 아는데 딱히 사용하지 않는 이유가 있다면 이런 말을 들을 필요는 없지만, 이후로 하루에 하나씩 고급 알고리즘 루틴을 막힘없이 완성하는 것을 목표로 한다면,

    어쩌면 컴퓨터 과학이나 계산수학 연구용의 프로토타이핑용 언어 같은 것을 하나 배워야 할지도 모르겠고요. 포트폴리오 용도라면 특히 시각화 같은 것은 필요할 테니 말이죠.

    0
  • 정만수
    75
    2019-06-22 15:48:08 작성 2019-06-22 15:50:59 수정됨
    0
  • 비비
    366
    2019-06-23 15:54:33 작성 2019-06-23 16:11:02 수정됨

    저는 이런거 기대했는데요.

    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
    #include <iostream>
    using namespace std;
     
    struct Node
    {
        int data;
        Node* left;
        Node* right;
     
        Node(int data) 
            : data(data), left(NULL), right(NULL)
        {
        }
    };
     
    void Insert(Node*& h, int element)
    {
        if (h == NULL)
        {
            h = new Node(element);
            return;
        }
     
        if (h->data > element) Insert(h->left, element);
        else Insert(h->right, element);
    }
     
    Node* Search(Node*& h, int element)
    {
        if (h == NULLreturn NULL;
     
        if (h->data > element) return Search(h->left, element);
        else if (h->data == element) return h;
        else return Search(h->right, element);
    }
     
    int main()
    {
        Node* tree = NULL;
     
        Insert(tree, 1);
        Insert(tree, 3);
        Insert(tree, 5);
        Insert(tree, 2);
        Insert(tree, 4);
     
        cout << Search(tree, 1)->data << endl;
        cout << Search(tree, 2)->data << endl;
        cout << Search(tree, 3)->data << endl;
        cout << Search(tree, 4)->data << endl;
        cout << Search(tree, 5)->data << endl;
     
        int i;
        cin >> i;
        return 0;
    }
    cs


    BFS, DFS, Tree Traversal 다 좋은데 이 부분은 다 Brute Force같은 느낌입니다.

    O(n) 순회 걸리는건 필요한 경우 쓰나, 자료구조할 때 Search는 무조건 O(lgn), O(1)아니면 의미 없어요.

    물론, 위의 코드에서는 void* 형이 아니고 int형으로 고정되어 있는데

    이 부분을 void*에서 int형으로 하기 위한 방법은 저도 별도로 공부안해봤네요.

    트리의 Inorder 순회의 경우, Stack이나 재귀적인 방법도 있지만 Threaded Binary Tree도 있고요.


    자료구조는 Stack, Queue, Binary Search Tree,

    Linked List, Heap, Hash Table, Balanced Tree 이후로는 잘 안물어봅니다.

    *특히, Heap 같은 건 제가 입사나 대학원 면접 볼 때 항상 나오던 개념이네요.

    가끔 탑티어 회사에서 Topological Sort 물어본다는 것 같은데,

    DFS 같은건 이 때 사용하면 되고, 이건 질문자님 나이에 안 물어볼 개념입니다.

    그때가서 배우면 될 것 같아요.


    마지막으로 만약에 제가 면접관이였는데,

    Binary Tree를 Inorder나 BFS해서 순회했다고 하면 저는 불합격시켰을 것 같아요.

    하나를 하더라도 제대로하는게 중요합니다.


    이 댓글로 자료구조를 모른다고 너무 자료구조만 공부하지 말고,

    운영체제, 컴퓨터 구조, 자료구조, 알고리즘, 네트워크 등 다양하게 공부하시면 될 것 같아요.

    저도 자료구조는 항상 주절 이야기하지만, 다른 분야에서는 문외한인게 가장 큰 약점이네요.


    물론, 자료구조나 알고리즘은 코딩테스트 때문에 어느정도 레벨까지는 공부해야되는게 사실입니다.

    저는 앞으로 수학공부랑 컴퓨터 cs 관련 공부하느라 바쁠 것 같아서, 이 스레드에는 댓글 안달겠습니다.

    위 같은 포트폴리오는 큰 플러스이고, 앞으로 자신이 목표로 하는 개발자가 되었으면 좋겠어요.

    0
  • 로그인을 하시면 댓글을 등록할 수 있습니다.