Computer Science
-
CS : Data Structure : Tree & GraphComputer 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) : 모든 왼쪽 자식 노드
-
CS : Data Structure : Stack & QueueComputer 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..