건빵의 블로그

앞에서 언급했던 Binary Search Tree의 단점을 생각해 보자. 트리가 skewed tree 또는 지그재그 트리 형태로 자라난다면 비효율적인 자료구조가 된다. 우리의 목적은 효율적인 자료구조를 만드는 것이기 때문에 뭔가 보완이 필요하다는 것을 알수가 있다. 그래서 나오는 것들이 Balanced Tree 종류이다. 트리의 Leaf들의 Depth들이 균형 잡힌 형태로 되도록 한다. 그 예로는 B-tree, AVL tree, Red-black tree 등등이 있으며 B-tree와 AVL tree에 대해서 공부해 보았다. B-tree의 성질은 다음과 같다. 1) B-tree는 BST와 같은 Search tree를 구성하되 각 노드가 여러 개의 엔트리를 가진다.(하나의 노드에 값 여러개) 2) 노드의 엔..

트리는 이산수학에서도 다뤘기 때문에 간단히 패스하고 지나간다. 기억을 되새길겸 짚어보자면 Tree는 Acyclic connected graph이다. 그리고 몇가지 특성들을 가지는데 그것은 패쓰~ 트리는 트리 자체도 중요하지만 트리의 응용으로 나오는 다른 트리들이 중요하다. Binary Tree는 각 노드가 차일드 2개를 가지며 left랑 right로 구별되는 트리이다. Full binary Tree는 모든 leaf의 depth가 같은 트리를 말한다. Complete Binary Tree는 Full binary tree에서 맨 오른쪽 leaf부터 순서대로 제거된 형태를 띄는 것을 말한다. 그리고 오늘의 주인공 Binary Search Tree는 각 노드 값이 왼쪽 서브트리의 값들보다 크고, 오른쪽 서브트리..

큐의 정의는 다음과 같다. a linear data structure of ordered entries such that entries can be inserted at one end (called the rear) and removed at the other end (called the front) 즉, 한쪽 끝에서 삽입이 일어나고 반대쪽 끝에서 삭제가 일어나는 선형 자료구조를 의미한다. LIFO(Last-In First-Out) 성질을 띄는 스택과는 다르게 FIFO(First-In First-Out) 성질을 띈다. 먼저 들어온 것이 먼저 나가는 형태를 띄며 일반적으로 줄을 서서 차를 탄다던가 하는 것을 생각하면 된다. 스택과 마찬가지로 응용분야 또한 아주 많다. 회문 인식하는데에 있어서 스택과 같이 ..

스택은 너무나 기본적이지만 유용한 자료구조이다. 스택의 정의는 다음과 같다. a linear data structure of ordered entries such that entries can be inserted and removed at only one end (called the top) 즉, top이라고 불리는 한쪽 끝을 통해 삽입과 삭제가 이루어지는 선형 자료구조이다. 그리고 스택은 ADT로써 어떠한 형태를 가지는(배열 혹은 리스트가 될수 있다) 데이터 엔트리를 가지고 push, pop, top과 같은 operation을 이용해서 해당 자료구조를 접근하고 조작한다. 기본적인 구조 자체는 워낙 간단하기 때문에 응용분야를 살펴보는 것이 중요할 것이다. 스택의 응용분야 중 가장 대표적인 것으로는 함수..

Data Structure의 정의는 위키피디아에 의하면 다음과 같다. Data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. 즉, 데이터를 저장하고 관리하는 것을 효율적으로 하기위한 특정한 방법을 말한다. 이 과목에서는 다양한 형태의 자료구조를 소개하며 그것을 실제로 구현하는 방법에 대해서도 다룬다. 그런 의미에서 중요한 것은 추상 데이터 타입(Abstract Data Type, ADT)의 개념이다. ADT는 어떠한 구조를 Data와 Operation으로 정의하고 Data의 접근은 그 ADT의 Operation으로만 가능하도록 한다. 그리고 내부 구조를 ..

오늘은 저녁에 놀아야 되니까, 좀 일찍 정리해보자 ㅋ Trees 트리는 Graph부분에서도 나왔지만 자료구조에서도 매우 중요하게 다뤄지는 중요한 개념이라 그런지 따로 언급된다. Graph부분에서는 트리는 acyclic connected graph라고 하였다. 또 다른 정의로써, tree는 모든 vertices의 쌍 사이에 유일한 path가 존재하는 ugraph이다. 또한 rooted tree는 지정된 root vertex를 가지고 모든 edge가 root로부터 directed away(?) 되는 트리이다. directed away는 정확한 해석은 모르겠지만 루트로의 길의 일부분이 된다? 정도로 받아들이면 될 것 같다. 이 부분에서 헷갈려야 하지 말아야 하는 것이 rooted tree와 tree이다. 우리..

어제 졸려서 못다한 정리 이어서 하기~ 이산수학에서 중점적으로 다뤄야 할 건 우리가 흔히 아는 그래프, 트리같은 것의 수학적 정의를 숙지하는 것이다. Graph undirected graph, 즉 ugraph는 edge가 2개 element의 쌍을 가지는 vertex의 subset인 경우를 말한다. 음. 즉 엣지가 set의 성질을 따르기 때문에 순서는 상관없다는 것을 의미한다. directed graph, 즉 digraph는 일반적으로 정의하는 그래프 같은 것으로써 엣지는 버텍스 간의 카티션 곱의 서브셋이다. 즉 버텍스간의 릴레이션이다. 수학적으로 표현하면, E⊆V×V 이다. 그리고 어떠한 Graph가 다이그래프일때, path는 vertices의 sequence로 정의되며 각각의 인접한 버텍스들 간에는 ..

오늘도 이산수학 공부하고 정리하기~ 중요한 것 위주로 정리하자. Relation 릴레이션은 Set 나오는 부분에서도 나왔지만 중요해서 그런지 따로 챕터가 있다. 어제 공부한 걸 정리할겸 되돌아보면 Relation은 두가지로 정의(표현)된다. 첫째는 R⊆A×B로써 표현되며 집합임을 나타내며, 둘째는 aRb 형태로 표현되며 infix binary boolean operator를 나타낸다. True or False 값을 가진다. Function 또한 앞에서 정의하였지만 Relation의 관점에서 다룬다. 함수는 (a,b)∈f일때 a에 대해 b가 하나만 존재하는 특수한 릴레이션이다. 따라서 위에서 언급했던 릴레이션의 두가지 표현방식으로 볼 때, a f b와 같이 표현하는것도 가능하다. 이 또한 T/F값을 가질 ..

2장은 기본적인 구조에 대해서 나온다. Sets 집합은 정렬되지 않은 object의 collection이다. 집합 내의 object는 element, member로 불린다. 어떠한 집합 A의 모든 멤버가 다른 집합 B의 멤버일 경우 A는 B의 부분집합이다. subset에서 equal을 제외한 것을 proper subset이라고 한다. 아.. 기호가 많은데 글로만 쓸려니 힘들다 'ㅁ' 어떠한 집합 S에 대해 |S|를 S의 cardinality 라고 하며 집합 S의 멤버의 갯수를 의미한다. 어떤 집합의 카디날리티가 유한하면, 유한집합이라고 하고.. 카디날리티가 무한하면, 무한집합이라고 한다. Power Set P(S)는 집합 S의 모든 부분집합을 원소로 가지는 특이한 집합이다. Cartesian produc..

방학들어 대학원 스터디의 본격적인 시작! 시간 날때마다 정리해 보자. Propositional Logic Proposition(명제)는 True 혹은 False 값을 가지는 문장이다. Proposition은 Proposition과 논리연산자들을 이용해서 재귀적으로도 정의된다.(negation, and, or, xor, implication 등등) 여기서 기억해둬야 할것은 p->q가 (not p) and q와 동일하다는것! 어떤 proposition이 항상 참인 것을 tautology라고 하며, 항상 거짓인 것을 contradiction, 그냥 일반적인 나머지 proposition을 contingency라 한다. 명제 p와 q에 대해서 pq 가 tautology면, p랑 q는 논리적으로 동등(logical..