TIL
Graph
위키피디아 (한글)
그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.컴퓨터 시스템에 그래프를 저장하는 방법은 여러가지가 있다. 자료 구조는 그래프 구조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다. 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하다. 하지만 실제 적용에 있어서 최적의 자료 구조는 이 두 구조의 조합된 형태를 띤다. 리스트 구조는 종종 sparse graphs에 적합하며 적은 메모리 공간을 요구한다. 행렬 구조는 많은 양의 메모리를 필요로하지만 더욱 빠른 접근을 제공한다.
- 이러한 구조는 프로그래머스에서 문제를 푸는와중에 자주 보곤 하였다. 그냥 문제 풀이 자체로만 인식하고 있었던 터라 이러한 구조에 관한것은 이번에서야 찾아보게 되었다. 그래서 아직은 그냥 그렇구나 하는 정도로 밖에 이해하지 못하였다.
- vertex(정점) : 위 그림에서의 파란점과 같은 부분
- edge(간선) : 정점과 정점을 이어주는 선 방향성이 없을 때는 무방향(위그림의 쌍방향 화살표). 방향성이 있을 때는 유방향 (위그림의 단방향 화살표).
Operations (영문 위키피디아 참조)
- adjacent(G, x, y): tests whether there is an edge from the vertex x to the vertex y;
- neighbors(G, x): lists all vertices y such that there is an edge from the vertex x to the vertex y;
- add_vertex(G, x): adds the vertex x, if it is not there;
- remove_vertex(G, x): removes the vertex x, if it is there;
- add_edge(G, x, y): adds the edge from the vertex x to the vertex y, if it is not there;
- remove_edge(G, x, y): removes the edge from the vertex x to the vertex y, if it is there;
- get_vertex_value(G, x): returns the value associated with the vertex x;
- set_vertex_value(G, x, v): sets the value associated with the vertex x to v.
- get_edge_value(G, x, y): returns the value associated with the edge (x, y);
- set_edge_value(G, x, y, v): sets the value associated with the edge (x, y) to v.
Tree
위키피디아 (한글)
트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
- 그냥 나무 뒤집은 모양으로 알고 잇으면 아래 나오는 이진 트리 구조 같은 부분에서 많이 보았던 경험이 있다. dom이 이러한 구조를 가지고 있다고 알고 잇고 그러한 돔을 자주 보긴하였으나 옆에서부터 펼쳐지는 모양이다 보니 시각적으로 바로 와닿지는 않는다.
용어 (영문 위키피디아 참조)
- Neighbor : Parent or child.
- Ancestor : A node reachable by repeated proceeding from child to parent.
- Descendant : A node reachable by repeated proceeding from parent to child. Also known as subchild.
- Branch node
- Internal node : A node with at least one child.
- Degree : For a given node, its number of children. A leaf has necessarily degree zero.
- Degree of tree : The degree of a tree is the maximum degree of a node in the tree.
- Distance : The number of edges along the shortest path between two nodes.
- Level : The level of a node is the number of edges along the unique path between it and the root node.
- Width : The number of nodes in a level.
- Breadth : The number of leaves.
- Forest : A set of n ≥ 0 disjoint trees.
- Ordered tree : A rooted tree in which an ordering is specified for the children of each vertex.
- Size of a tree : Number of nodes in the tree.
Binary Search Tree
위키피디아(한글 [그림은 영문]) 참조
컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.
- 각 노드에 값이 있다.
- 값들은 전순서가 있다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
- 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
- 레슨 내용을 읽고 코플릿도 풀어보고 대략적인 활용 법도 알지만 정리는 잘모르겟다. 좀더 익숙해진 뒤에는 말끔하게 정리할수 있기를.
오늘 한 것
- 자료 구조 코플릿 풀기 완료
- 후기 공유회 참석
To do
-
node.js를 이용한 서버관리나 서버와 클라이언트 간의 정보 교환 등 미리 공부할수 있는 부분에 집중해보는것도 좋은 선택이라고 생각한다.
-
scss 도 활용을 생각해보면 좋을것 같다.
-
typescript 공부 예제를 생각해보자
오늘은...
아침부터 페어프로그래밍으로 시작하였다. 자료구조 코플릿 생각외로 시간을 상당히 소모 하였다. 트리 구조를 맛보기로 체험하는 코플릿은 수월하게 진행하였으나 그래프를 맛보기로 보는 코플릿에서는 문제를 제대로 이해하지못한 긴시간 소모하고도 완수 하지 못하였다. 점심이후로도 그러한 고난은 지속 되었으나 정규 시간 마무리전부터는 급속도로 진행할수 있었다. 그리고 그래프에 관련된 다른 문제를 풀던 와중 그래프 맛보기에선 문제자체를 잘못 이해한것을 깨닿게 되었다. 그리고 다시 이해한 방식으로는 허무하게 종결. 문제를 이해하는 부분의 주용성을 다시금 깨닿게 된 하루였다.
