트리는 이산수학에서도 다뤘기 때문에 간단히 패스하고 지나간다. 기억을 되새길겸 짚어보자면 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..
이해하기 쉽게 받아들이자면, 자신에게 들어오는 edge가 없는 순서대로 정렬하는 것이다. 즉, 자신에게 dependency가 없는 순서대로 정렬한다! 사이클이 있을 경우 topological sort가 존재하지 않는다. 당연하다! 사이클이 있다는 것은 서로 의존성이 있는 것일테니까~ 사용되는 예로는 Compiler의 Syntax directed Translation에서 각 attribute의 dependency를 구하는 데 사용한다. 그 순서대로 attribute가 계산되는 순서를 정한다. 어떠한 그래프에 대해 여러 개의 topological sort가 존재 가능하다. 아래의 그림에서 다음과 같은 sort가 가능하다. 7, 5, 3, 11, 8, 2, 9, 10 3, 5, 7, 8, 11, 2, 9, 1..
- Total
- Today
- Yesterday
- 대학원
- linux
- Reverse Engineering
- 리눅스
- 안드로이드
- operating systems
- 운영체제
- 기계학습
- Data Science
- 머신러닝
- 이산수학
- 데이터 과학
- 알고리즘
- statistical learning
- Machine Learning
- android
- 데이터 사이언스
- reversing
- Discrete Mathematics
- 카타르
- 개발
- Data Structure
- 리버싱
- 자료구조
- 리버스엔지니어링
- Algorithms
- java
- 카타르 음주
- 자바
- 통계학습
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |