value = able

분류 전체보기

• CS : Algorithm : 최소 비용 신장 트리(MST)

  Computer Science/Algorithm, Data Structure 2021. 4. 15. 16:51

  Spanning Tree (스패닝 트리, 신장 트리) 1. 그래프 내의 모든 정점을 포함하는 트리 2. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)이고, (n-1)개의 간선으로 연결된 그래프는 필연적으로 스패닝 트리가 된다. 3. 하나의 그래프에는 많은 스패닝 트리가 있다. MST (Minimum Spanning Tree) 1. spaniing tree 중, 간선의 가중치의 합이 최소인 트리 2. n개의 정점을 가지는 그래프에 대해서, 반드시 (n-1)개의 간선만 이용해야 한다. 3. 구현 종류 Kruskal MST 알고리즘 Prim MST 알고리즘 Kruskal MST 알고리즘 1. greedy method를 활용하여 모든 정점을 최소의 가중치로 연결..

  Read More

• CS : Data Structure : Tree & Graph

  Computer Science/Algorithm, Data Structure 2021. 4. 15. 16:46

  Tree 1. 노드(node)와 노드를 연결하는 간선(edge)으로 이루어진 자료 구조이다. 2. 하나의 루트 노드(root node)를 가진다. 루트 노드는 0개 이상의 자식 노드를 가진다. 3. 트리에서는 사이클(cycle)이 존재할 수 없다. 4. 그래프(graph)의 한 종류이고, 트리를 '사이클이 없는 하나의 연결 그래프'라고 표현할 수 있다. 5. 노드의 수 : N 간선의 수 : N-1 6. 임의의 두 노드 간의 경로는 유일하다. 7. 종류 이진 트리 (Binary Tree) : 각 노드가 최대 두 개의 자식을 갖는 트리 이진 탐색 트리 (Binary Search Tree) : 모든 왼쪽 자식 노드

  Read More

• CS : Data Structure : Heap

  Computer Science/Algorithm, Data Structure 2021. 4. 15. 16:24

  Heap 1. 완전 이진 트리의 한 종류이다. 우선순위 큐를 위해 만들어진 자료구조이다. 2. 여러 개의 값들 중, 최댓값이나 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조이다. 3. 힙은 중복 값을 허용한다. 4. max heap : key(부모 노드) >= key(자식 노드) min heap : key(부모 노드)

  Read More

• CS : Data Structure : Stack & Queue

  Computer Science/Algorithm, Data Structure 2021. 4. 15. 16:22

  Stack 1. 한 쪽 끝에서만 자료를 넣고 뺄 수 있는, LIFO(Last In First Out) 구조이다. 2. pop() : 스택에서 가장 위의 항목을 제거한다. push(item) : item을 스택의 가장 윗 부분에 추가한다. peek() : 스택의 가장 위의 항목을 가져온다. (제거 아님) isEmpty() : 스택이 비어있는지 여부를 반환한다. 3. 재귀 알고리즘을 사용하는 경우에 스택이 유용하다. 재귀적으로 함수를 호출할 때, 임시 데이터 값을 스택에 넣어준다. 이 후, backtracking 시 스택의 값을 참조한다. Queue 1. 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조이다. 2. add(item) : item을 큐의 끝부분에 추가한다. re..

  Read More