본문 바로가기

전체 글

 (64)
Huffman tree 1. Huffman Coding Trees 1-1. 문제 상황 ASCII codes : 문자 하나당 8bit가 사용되는 크기가 고정된 코딩방법 자주 사용하는 문자를 더 적은 수의 비트로 코딩하면 공간을 줄일 수 있다. variable-length coding : 문자별로 길이를 다르게 하는 코딩 목표 : external path weight이 최소가 되는 binary tree를 구하는 것 weighted path length of a leaf : weight $\times$ (depth of the leaf) external path weight = weighted path length의 합 1-2. Huffman tree 생성 과정 1) frequency 중에서 가장 작은 것 두개를 찾는다. 2) 그 ..
Priority Queue & Heap 1. Priority Queue 1.1 문제 상황 삽입은 자유롭게 이루어지지만, element를 꺼낼 때 항상 가장 큰 element(removemax)를 꺼내고자 한다면 가장 좋은 자료구조는 무엇인가? ex) multi-tasking operating system에서 scheduling job하는 문제! 1.2 Unsorted array or linked list insert : O(1)의 시간 소요 removemax : max인 element를 찾기 위해 O(n)의 시간 소요 1.3 Sorted array of linked list insert : O(n)의 시간 소요, sorting을 위해 removemax : 맨끝 값을 return하면 되니까 O(1) 하지만 이때 heap 자료구조를 사용하게 되면..
Combinational Logic Technology 1. Random logic 1-1. 구현 우리가 흔히 아는 NAND나 NOR gat들을 뜻한다. 1-2. 단점 (1) 논리 구현에 필요한 최소한의 블락 수를 결정하기가 쉽지 않음 (2) 논리의 변경이 있을 때 전체 디자인 자체를 바꿔야 한다. => 변경이 굉장히 어려움 (3) 설계 디자인만 보고 어떤 logic(truth table)을 가지고 있는지 알아내기 어렵다. 2. Regular logic 2-1. 장점 (1) 디자인을 빠르게 할 수 있다. (2) 변화가 있을 때 빠르게 적용할 수 있다. (3) 디자인을 보고 어떤 논리를 가지고 있는지 유추하기가 쉽다. trade-off : 완전 최소의 디자인보다는 cost가 많이 든다. 구현을 위해 Multiplexer, Demultiplexer를 사용해서 w..
Relation & Function 1. Relation 1-1. Partition and Covering of a set $\pi = \{A_1, A_2, ... , A_m\}$ 일 때, $A_i (1 \le i \le m)$이 S의 non-empty subset이고, $\bigcup_{i=1}^m A_i = S$이면 set $\pi$를 covering of S라고 부른다. $A_1, A_2, ... , A_m$을 S를 cover라고 부른다. 만약 $\pi$의 element들이 서로 disjoint라면 $\pi$를 S의 partition이라고 부른다. $A_1, A_2, ... , A_m$을 S를 the blocks of the partition이라고 부른다. 1-2. Quotient Set R이 equivalence relation o..
Binary Tree(이진 트리), Binary Search Tree(이진탐색트리) 1. Binary Tree 1-1. 정의 유한개의 노드로 이루어진 트리이다. 이진 트리는 root(노드)와 그와 이어진 두개의 이진트리들로 구성된다.(이를 각각 left, right subtree로 칭한다.) 1-2. 용어 (1) node : 이진 트리를 구성하는 단위 value를 저장하는 공간과 왼쪽과 오른쪽을 노드를 가르치는 포인터로 구성된다. (2) children : root 노드의 왼쪽과 오른쪽이 가리키는 node를 child라 한다. (3) edge : root들을 잇는 선분 (4) ancestor : children의 반대 (5) descendant : 밑의 노드들 (6) path : 이웃하는 두 노드가 앞이 부모, 뒤가 자식인 노드의 열 (7) level(=depth) : 루트 노드에서 자..
Java inheritance(상속) 1. inheritance(상속)이란? 하나의 클래스가 다른 클래스의 특징을 상속받은 채로 설치되는 것 종의 분류와 비슷하다고 볼 수 있다. 2. Inheritance(상속)의 장점 2-1. 모듈화 하나의 클래스를 잘 설치해두면 그 클래스를 기반으로 다른 클래스를 생성할 수 있다. 만약 수정 사항이 생기면 최상위 부모 클래스만 수정하면 그에 따른 수정 결과가 자식 클래스에게 상속됨 2-2. 재사용성 겹치는 attribute나 method가 있을 때 번거롭게 코드를 두 번 쓰지 않아도 된다. 3. Inheritance(상속) 사용 문법 extends를 이용해서 상속을 수행할 수 있다. class Point{ int x, y; public void move(int dx, int dy){x += dx; y +..
Java Encapsulation 1. Encapsulation의 정의 해당 클래스의 구현 과정을 모두 드러내지 않고, 만약 다른 사람이 접근하면 안되는 variable이나 method의 경우 접근 제한자를 통해서 접근을 관리할 수 있음! 2. 접근 제한자(Access Modifier)의 종류와 권한 2-1. public 모든 곳에서의 접근을 허용 2-2. protected 같은 패키지에 있는 객체와 상속 관계의 객체들만 허용 2-3. default 같은 패키지에 있는 객체에서만 허용 2-4. private 현재 객체 내에서만 사용 가능 2-5. Getter와 Setter private attribute의 값을 반환하고, 설정할 수 있는 method. convention으로 설정되어 있다. class person{ private int ..
Java OOP(Object Oriented Programming) 1. OOP란? 1-1. OOP의 정의 Programming을 Object들끼리 interaction하는 관점으로 프로그래밍을 하는 방법을 뜻한다. 이게 당최 무슨 소리냐? 우선 하나씩 바라보자. object란 자바에서의 데이터들에 속하고, Class라는 틀에 의해 만들어지는 제품이라고 생각하면 되겠다. 예를 들어 슈크림 붕어빵, 팥 붕어빵, 녹차 붕어빵(Object),,,,등등이 같은 붕어빵 틀(Class)에 의해 만들어지는 것처럼 다른 Java의 Object들도 하나의 Class에서 생성되게 된다. 1-2. Class의 특징 Class는 Attribute와 Method를 가진다. Attribute는 Class의 Object들이 공유하는 특징들이고(예를 들면 student 클래스라면 학번, 나이, 성별..

티스토리툴바