개발하는 멍정이야기

Graph Theory - 그래프는 G = (V, E)의 두 요소로 구성된다. - vertex : 정점 - E : 간선들의 집합 | 간선들은 2개의 endpoint를 가진다. - directed graph(digraph) : 방향성이 있는 그래프 - weighted graph(weights) : 값이 있는 그래프 - path : digraph에서 정점에서 목적지로 가는 방법(정점들을 담고 있는?) - cycle : path가 돌아서 시작점으로 돌아옴 ㄴcycle인 그래프를 cyclic, 그렇지 않으면 acyclic - simple : 같은 정점을 다시 돌아오지 않는 경우 - length : weighted graph에서 weights들의 합 Example : A weighted, directed grap..

Dynamic Programming (동적 계획법) Bottom up 방식으로 작은 값 부터 구하기 시작하여 결과를 도출한다. 작은 값부터 시작하는건 DIvide and Conquer랑 비슷하시지만 밑에서부터 시작한다는 점에서 차이점이 있다. Bottom up 방식이기 때문에 한 번 계산한 결과를 다시 계산할 필요 없이 저장된 결과를 불러서 사용한다. The Binamial Conefficient(이항계수) 조합 n​Cr n개에서 r개를 순서 상관없이 골라내는 경우의 수 전체 경우의 수 n! 에서 필요없는 나머지 경우의 수 (n-1)!을 나누고 순서가 상관 없기 때문에 뽑은 갯수 k!만큼 또 나눠주기~ Pascal's Triangle 대각선 위에 있는? 값들의 합은 아래에 있는 값이 된다! 조합을 사용해..

Matrix Multiplication : 행렬의 곱은 어떻게 계산 할까 //Matrix Multiplication //Standard Algorithm void matrixmult(int n, const number A[][], const number B[][], number C[][]) { index i, j, k; for (i = 1; i 결과적으로 DIvide and Conquer이 되는 것!! strassen(행렬 A, 행렬 B, 새로운 행렬 C) { if(일반적인 계산이 더 이득일 것 같은 경우) 일반적으로 C = A * B를 계산해줌 else { //계산이 복잡한 경우 행렬 A를 4개의 행렬로 나눠줌 행렬 B를 4개의 행렬로 나눠줌 step1. M1부터 M7까지의 경우를 호출함 ex1. st..

Quicksort 가장 첫번째 array의 값(pivot)을 기준으로 더 작은 값과 큰 값으로 나누어 정렬함 //Quicksort void quicksort(index low, index high) { index pivotpoint; if(high > low) { partition(low, high, pivotpoint); //pivotpoint를 기준으로 정렬 quicksort(low, pivotpoint-1); // pivot보다 큰거 quicksort(pivotpoint+1, high); //pivot보다 작은거 //partition void parititon(index low, index high, index &pivotpoint) { index i, j; keytype pivotitem; piv..

The Master Theorem(마스터 정리) 이런 경우에서 시간복잡도를 편하게 구할 수 있는 공식! where a > b> 1 and n is a no -negative integer. case1. a - ε라면 시간복잡도는 오른쪽과 같다. case2. a랑ε가 같은 경우 시간복잡도는 오른쪽과 같다. case3. a + ε이고 중간의 수식을 만족하는 C가 1보다 작다면 시간복잡도는 오른쪽과 같다. Example case1 case2 case3 Auxiliary Master Theorem case3의 C < 1을 만족하지 못하는 경우

DIvide and Conquer Approach - Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다. - Conquer : 작아진 인스턴스를 해결한다. - Combine : 해결한 인스턴스를 재조립한다. -> Top-down approach(하향식 접근법) Binary Search Algorithm Design - 검색 범위를 줄여가며 탐색 - Problem : 크기가 n인 sorted array S에서 key x는 어디에 있는가? - Input(parameter) : 양수 n, 1부터 n까지의 값을 갖고 있는 정렬된 내림차순이 아닌 배열 S(sorted array) + non-decreasing order(비내림차순) : 내림차순이 아니다 != 오름차순 ex. 1, 5, 6..

컴퓨터 그래픽스 컴퓨터를 사용하여 그림을 생성하는 기술 2D Graphics - 점, 선, 원, 곡선 등과 같은 기본 도형을 이요하여 2차원 평면 상에 그림 - 결과물을 픽셀의 형태로 표현 Verctor Graphics - 그래픽에 사용된 객체들을 수학적 함수로 표현하여 기억 공간에 저장하는 방식 - 파일의 크기가 래스터 그래픽 방식으로 저장한 것 보다 작음 - 기하학적 객체를 수식의 형태로 표현하므로 화면 확대 시에도 화질의 변화가 없음 Raster Graphics - 래스터 그래픽 출력장치에 표시하기 위한 그래픽 데이터를 픽셀단위로 기억 공간에 저장 - 출력장치의 해상도에 따라 파일의 크기가 다름 - 확대시 화질이 깨짐 3D Garphics 모델링(Modeling) : 물체의 기하학적인 형상을 만드는..

리눅스란 무엇일까? 리눅스는 컴퓨터 운영체제(OS)라고 할 수 있습니다. OS는 간단하게 하드웨어를 작동시키기 위한 소프트웨어 시스템이라고 생각하면 이해하기가 쉽습니다. 가까운 곳에서 찾아보면 windows, Mac OSX, iOS, Linux 등을 언급할 수 있습니다. 간단하게 윈도우를 사용하여 운영체제가 하는 일을 살펴봅시다. -> 구체적으로 말하면 운영체제의 커널(kernal)을 담당하고 있습니다. 운영체제는 무엇을 할까? with window 간단하게 운영체제에 대해 알아봅시다. 윈도우 컴퓨터에서 볼륨을 조절하거나, 폴더에 파일을 저장하거나, 인터넷에 연결하는 일들이 운영체제에서 하는 일이라고 할 수 있습니다. 하드웨어와 소프트웨어를 관리하는 시스템이기 때문입니다. 좀 더 구체적으로 살펴보면 운영..

SSD에 대해 알아보자. Overall Architecture - Flash memory : 데이터 저장 - SSD Controller : 전체적인 SSD 시스템 제어 (flash memory에 있는 값을 꺼내오거나 넘겨주거나..) - RAM Buffer(DRAM?) : SSD에서 필요한 연산을 도움 - Host-storage Interface : host와 SSD를 연결, I/O를 주고받음 ex. sata NAND Flash Chip (Package) 무언가 전하량을 잘 옮겨서 경우의 수를 잘 만든다네요. page는 block들로 이루어져있고, block은 page로 이루어져있고 page는 데이터를 다루는(I/O) 최소 단위이다. Host-Storage Interface Physical connecti..

Big O (빅오) 정의 : 점근적 상한선 주어진 복잡도 함수 c×f(n)에 대해 음이 아닌 정수 n이 N보다 크고 양수인 정수 c가 존재한다면 O(f(n))은 g(n)보다 큰 함수들의 집합이다. => g(n) ≤c×f(n) g(n)이 알고리즘에 대한 시간복잡도라면 결국 알고리즘의 시간복잡도의 최대값은 f(n)보다 클 수 없기 때문에 g(n)은 O(f(n))이라고 할 수 있다. -> g(n)은 c×f(n)보다 느리게 실행될 수 없기 때문 ∴ g(n)의 시간복잡도는O(f(n))이다. Example take c = 11 and N = 1 => 1^2+10*1 == 11(1^2)take c = 2 and N = 10 => 10^2+10 < 2(10^2) 아무튼 이런 시간복잡도를 갖고 있는 알고리즘은 n^2의 ..