시냅스

이진 탐색 트리, Binary search tree 이진 탐색 트리는 각 노드에는 값이 있다. 값들은 전순서(임의의 원소를 비교할 수 있는 부분 순서 집합)가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지신 노드들로 이뤄진다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이워진다. 이진 탐색 트리는 일반적으로 탐색에서 O(log n)으로 장점을 갖는다. 다만, 편향 트리로 이뤄져있다면 O(n)의 가능성이 있다. 이 경우 red black tree를 이용할 수 있다. 아래에서는 Linked list를 사용한 이진 탐색 트리의 구현을 살펴본다. 구현 생성 삽입 개별 node 삭제 Tree 삭제 생성 typedef struct BinSearchTreeNodeType..

힙 Heap 힙은 항상 완전 이진 트리 (위로부터 왼쪽 오른쪽 순서대로 쌓이는 것을 말한다.)의 형태를 지닌다. 부모의 값은 자식의 값보다 크거나(Max heap), 작아야(Min heap) 한다. 따라서 루트노드에는 항상 데이터 중 크거나 작은 값이 저장되어 있기 때문에 최대, 최소값 탐색에 O(1)이 걸린다. 데이터의 삽입과 삭제는 모두 O(log N)이 소요된다. 이러한 특성은 완전 이진 트리이며, 부모노드가 항상 크거나 작다는 확증에 기인한다. Max heap 구현 생성 삽입 root node 반환, Pop Heap 삭제 생성 typedef struct HeapNodeType { int key; } HeapNode; typedef struct HeapType { int maxElementCount..

파일 디스크립터 (File Descriptor) Unix OS에서 모든 것은 파일로 관리되는데 이러한 파일에 접근할 때 파일 디스크립터 라는 개념을 이용한다. 파일은 일반적인 정규 파일, 디렉토리, 소켓, 파이프, 블록 디바이스, 캐릭터 등등 모든 객체들을 파일이라 칭한다. 0을 포함한 양수인 정수만을 값으로 하고, 0 : 표준 입력 (Standard Input, STDIN_FILENO) 1 : 표준 출력 (Standard Output, STDOUT_FILENO) 2 : 표준 에러 (Standard Error, STDERR_FILENO) 를 기본적으로 할당 받는다. FD는 숫자로, FD 테이블의 인덱스를 의미하기 때문에 FD가 3으로 반환됐을 경우, File Descriptors table에 3번 항목이..

Makefile에 앞서... 컴파일 단계 1. Preprocessor (전처리 단계) 전처리기가 전처리기 지시자(헤더, 매크로)를 처리한다. 소스코드를 담고있는 c파일로부터 i를 생성한다. .c -> .i 2. Compiler (컴파일 단계) 전처리된 파일에서 .i -> .s를 생성한다. .s 파일은 어셈블리어 코드로 이루어져 있다. 3. Assembler (어셈블 단계) .s -> 기계어로 이루어진 .o 생성 4. Linking (링킹 단계) .o (object) 파일은 라이브러리 함수가 없기 떄문에 라이브러리와 .o 파일을 링킹하여 .exe 파일을 생성한다. Makefile Makefile을 통해 컴파일 단계들을 대량으로 제어하거나, 처리하기 쉽게 할 수 있다. 중요한 키워드는 Incremental ..

함수 헤더 파일 설명 strlen(문자열포인터); strlen(문자배열); string.h 문자열의 길이를 구합니다(NULL은 포함하지 않음). strcmp(문자열1, 문자열2); string.h 문자열1과 문자열2를 비교합니다(Windows). - -1: ASCII 코드 기준으로 문자열2가 클 때 - 0: ASCII 코드 기준으로 두 문자열이 같을 때 - 1: ASCII 코드 기존으로 문자열1이 클 때 앞에 것이 크면 1, 뒤에 것이 크면 -1입니다. 리눅스와 OS X에서는 문자열1의 ASCII 코드값에서 문자열2의 ASCII 코드값을 뺀 결과를 반환합니다. - 반환값이 양수가 나오면 문자열1이 크고, 음수가 나오면 문자열2가 큼 - ASCII 코드 기준으로 두 문자열이 같으면 0 strcpy(대상문자..

포인터 : 메모리 상에 위치한 특정한 데이터의 (시작) 주소값을 보관하는 변수 포인터에도 형이 있다 메모리를 효과적으로 사용하는 기술 메모리 관리 - 간접 주소 지정 방식 자신이 사용하고 싶은 메모리의 '주소'를 저장하고 있는 메모리가 포인터 32bit -> 4btye 64bit -> 8byte int 형 데이터의 주소값을 저장하는 포인터와, char 형 데이터의 주소값을 저장하는 포인터가 서로 다르다. 'ptr = ' : 포인터 변수의 값(가리키는 대상의 주소)이 변경 '*ptr = ' : 포인터가 가리키는 대상의 값이 변경 포인터를 사용하여 간접 주소 방식으로 값을 대입하는 이유? 모든 변수가 같은 함수에 선언되는 것은 아니기 때문 일반 변수는 다른 함수에 있는 변수 사용 불가 포인터 변수는 다른 함..