나만의 깍두기판

1. 그래프 개념과 ADT1) 기본 개념(1) 정의와 용어- Graph 자료 구조: 상하위 개념이 없는 노드와 노드들을 잇는 엣지로 구성되어 있는 자료구조이다.- Graph에서는 모든 노드들이 관계를 가지고 있을 필요가 없어 비교적 자유로운 구조이다. (2) 특징- Graph는 비선형(non-linear)적이며, network model이라고도 불린다.- 노드는 방향성이 있기도 하고 없기도 해서 각각을 '무방향성 그래프', '방향성 그래프'라고 나뉘어 부른다.- 실생활에서는 지도나 지하철 노선도, 페이스북 친구 추천이나 e-commerce 추천 알고리즘이 있다.   2) 그래프 추상 데이터 타입(1) 그래프의 정의 (2) 무방향 그래프: 간선을 표현하는 두 정점의 쌍에 순서가 없는 그래프(3) 방향 그래..

1. 이진 탐색 트리1) Binary Search by Array(1) ConceptQ. 서로 다른 n개의 정렬된 수가 list에 저장되어 있을 때, 특정한 값을 찾아라A. Description of the binary search problem   2) Binary Search Trees(1) 정의: Binary Search Tree는 탐색에 목적을 둔 binary tree이다. 본 tree는 empty일 수 있고, empty가 아닌 경우는 다음의 성질을 만족한다.1️⃣모든 element는 서로 다른 key를 갖는다.2️⃣Non-empty left subtree에 있는 key들은 root의 key보다 작은 값을 갖는다.3️⃣Non-empty right subtree에 있는 key들은 root의 key보..

1. 트리 항해1) Binary Tree Traversal(1) 정의- Tree의 각 node를 한 번씩 방문하는 알고리즘- 각 node와 그 node의 subtree들을 동등하게 취급하면 6개의 traversal 조합이 있다.(L: Left로 움직임, V: 노드를 visiting, R: Right로 움직임)1️⃣LVR 2️⃣LRV 3️⃣VLR 4️⃣VRL 5️⃣RVL 6️⃣RLV - Traverse left before right를 도입하면, 3개의 조합이 남는다.  (2) In-order Traversals(중위 순회)- 방법: 왼쪽 branch를 모두 방문한 후, node를 방문하고, 오른쪽 branch를 방문함  (3) Pre-order Traversals(전위 순회)- 방법: node를 방문하고..

1. 트리 개념1) 정의: 다음의 성질을 가진 하나 이상의 node로 이루어진 finite set이다.Root라고 불리우는 특정 node가 있다.나머지 node들은 n개(n >= 0)의 disjoint set인 T1, T2, ... Tn으로 분할된다. 이때 각 set는 Tree이다.T1, T2, ... Tn를 root의 subtree라고 부른다.2) 트리는 root를 가진 acyclic graph(비순환 그래프)이고, 계층적 구조를 가진다.    3) Sample Tree로 알아보는 개념 (1) Node의 degree(자식 수) : node의 subtree 수를 말한다.A, D는 3B, E는 2C, H는 1K, L, F, G, M, I, J는 0(2) Tree의 degree: tree에 있는 node의 ..