Advanced Selection Algorithm 개선된 선택 알고리즘 - 일반적인 선택 알고리즘과 같이, 입력값들중 i번째로 작은(큰) 원소를 찾는 알고리즘이다. - 개선된 선택 알고리즘은 \(\texttt{partition()}\) 함수가 수행하는 분할의 균형을 어느정도 보장함과 동시에, 그에 따른 Overhead까지 통제하여 최악의 경우에도 선택 알고리즘이 \(\Theta(n)\)에 수행되도록 한다. Background (배경지식) * Selection Algorithm (선택 알고리즘) (URL) * Quick Sort (퀵 정렬) (URL) - 일반적인 선택 알고리즘의 경우, \(n\)개의 입력값들에 대해 평균적으로 \(\Theta(n)\)에 비례하는 시간이 소요되고, 최악의 경우, \(\Th..
Selection Algorithm 선택 알고리즘 - 입력값들중 \(i\)번째로 작은(큰) 원소를 찾는 알고리즘이다. - \(n\)개의 입력값들에 대한 전체적인 검색이 필요하기 때문에 \(\Omega(n)\) 만큼의 실행시간이 요구된다. - 가장 우수한 일반 정렬 알고리즘의 성능이 \(O(n\log n)\)이기 때문에, 선택 알고리즘의 실행 시간은 적어도 \(O(n\log n)\) 과 같거나 더 우수해야 한다. Time Complexity: 평균적으로 \(\Theta(n)\), 최악의 경우 \(\Theta(n^2)\) Background (배경지식) * Quick Sort (퀵 정렬) (URL) [Algorithms] Quick Sort | 퀵 정렬 Quick Sort 퀵 정렬 - 퀵 정렬은 고급 정렬 ..
SOP and POS Forms SOP와 POS 형식 SOP (Sum of Products) - All products are the products of single variables. \(\mathrm{ex)} \; f(A, B, C) = AB' + A'BC\) SOP에 해당된다. \(\mathrm{ex)} \; f(A, B, C) = A \cdot (B + C') + A'B'\) SOP가 아니다. (\(B + C'\)이 Single variable이 아니기 때문이다.) \(\mathrm{ex)} \; f(A, B) = A + B'\) SOP에 해당된다. POS (Product of Sums) - All sums are the sums of single variables. \(\mathrm{ex)} ..
Boolean Algebra 불 대수 - Boolean algebra provides the theoretical foundation for digital logic design. - 순서론과 추상대수학, 논리학에서, Boolean algebra는 어떤 명제의 참과 거짓을 이진수 1과 0에 대응시켜서 명제와 명제간의 관계를 수학적으로 표현하는 것이다. - 논리적 공리들을 만족시키는 논리합과 논리곱 및 부정의 연산이 정의된 대수 구조이다. Notation (표기법) \(A \iff B\) - 식 A와 식 B가 동치(Equivalent; 논리적으로 같음)임을 의미한다. \(A \land B \iff A \cdot B \iff AB\) - A AND B의 의미로, 두 변수 사이에 논리곱(\(\land\))을 ..
Introducing Python(처음 시작하는 파이썬) Chapter 6. 객체와 클래스 6.1 What Are Objects? (객체란 무엇인가?) - 파이썬에서는 숫자에서 모듈까지 모든 것이 객체이다. - 객체는 어떤 구체적인 것의 유일한 Instance이다. * Object(객체) = Data(데이터) + Code(코드) - Data = Variable = Attribute - Code = Function = Method 6.2 Define a Class with class (클래스 선언하기: class) class Person(): # Person 클래스 정의 def __init__(self, name): self.name = name ... someone = Person('Elmer Fudd'..
Smart Pointer Template Class 스마트 포인터 템플릿 클래스 - Smart Pointer는 포인터에 몇 가지 기능이 추가된 클래스 객체를 의미한다. - 특히, 동적으로 메모리를 할당받은 포인터가 수명을 다했을 때, 자동으로 메모리를 반납해주는 기능을 지원한다. (이런 이유로, 스마트 포인터 객체는 Heap 공간 이외의 메모리를 가리키는 포인터를 받아들일 수 없다.) - 스마트 포인터 클래스는 memory 헤더 파일에 정의되어 있다. - 스마트 포인터 클래스 이름은 std 이름 공간에 포함되어 있다. - 스마트 포인터는 아래와 같이 3개의 스마트 템플릿으로 구성된다: auto_ptr unique_ptr shared_ptr - 위 스마트 포인터 모두 내부적으로 new를 통해 주소를 얻고,..
string Class string 클래스 ※ C/C++에서는 크게 두 가지 문자열 처리 패러다임이 있다. 1. C-Style Strings - cstring (string.h) 헤더파일에 C-Style 문자열 처리 함수들이 정의되어 있다. - C언어에서 익히 사용했던 strcmp(), strcpy() 함수 등이 C-Style 문자열 처리 함수에 해당된다. 2. string Class - string 헤더파일에 string 클래스의 Specification이 정의되어 있다. - 문자열 대입/결합/비교, 개별 문자에 대한 접근, 문자열을 구성하는 문자나 부분 문자열에 대한 검색 등을 지원하는 연산자가 오버로딩 되어있고, 여러 가지 Constructor들과 메서드들이 정의되어 있다. - string 객체는 ..
만들면서 배우는 Git/GitHub 입문 Chapter 5. 원격 저장소와 Git - Git에서는 원격 저장소와 로컬 저장소 사이의 소통을 위한 기능을 제공한다. * 저장소 간 소통을 위한 Git 명령어 명령어 기능 git clone 원격 저장소의 모든 내용을 로컬 저장소로 복사한다. git remote 로컬 저장소를 특정 원격 저장소와 연결시킨다. git push 로컬 저장소의 내용, 변경 사항을 원격 저장소로 보낸다. git fetch 로컬 저장소와 원격 저장소의 변경 사항이 다를 때, 이를 대조하고 git merge 명령어와 함께 최신 데이터를 반영하거나 Conflict 등을 해결한다. git pull gir remote 명령을 통해 서로 연결된 원격 저장소의 최신 내용을 로컬 저장소로 가져오면서 ..
