이번 장에서는 균형 이진 탐색 트리로 많이 사용되는 RB tree를 C언어로 구현해본다. 여기서 구현하는 ADT(Abstract Data Type)은 ordered set, multiset이다. 구현해야 하는 기능들은 CSLR 13장의 수도 코드를 구현하면 되는데, 구현해야 할 기능들은 다음과 같다. new_tree() : RB tree 구조체를 생성한다. 이때, 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야한다. Tree를 생성할 때는 여러 개의 tree를 생성할 수 있어야하며, 각각 다른 내용들을 저장할 수 있어야 한다. 이를 tree 구조체의 동적 할당이라고 한다. 또한 RB tree의 leaf 노드는 nil 노드라는 것으로 표시해야 하는데, nil 노드는 일종의..
우선 클론하고자 하는 깃 리포지토리에 bare 옵션을 붙여서 클론해준다. $ git clone --bare https://github.com/krafton-jungle/rbtree-lab.git 여기서 bare 옵션은 GIT repository 를 bare 로 만든다. 즉 를 생성하고 /.git 을 생성하는 대신에 자체를 $GIT_DIR 로 만든다. 그리고 해당 깃 디렉토리로 이동하여 mirror 옵션을 사용하여 원격 저장소의 복사본을 만든다. 이는 --bare 옵션을 포함한다. $ cd ${project_name}.git # 아래 repository는 GitHub미리 만들어 놓아야 함 $ git push --mirror https://github.com/${깃헙ID}/rbtree-lab.git 그리고 ..
우분투에서 우선 다음 명령어들을 수행하여 개발 환경을 설치할 수 있다. $ sudo apt update $ sudo apt upgrade $ sudo apt install gcc make valgrind gdb # gcc, make 등 개발 환경 설치 $ sudo apt install gcc-multilib. # 32-bit lib 그리고 우분투에서 깃을 사용할 때, github login으로 인해 복잡해지지 않도록 Github CLI를 설치해야 한다. 설치 후에는 gh auth login 명령으로 access token 을 생성 혹은 설치하면 된다. $ curl -fsSL https://cli.github.com/packages/githubcli-archive-keyring.gpg | sudo dd o..
이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성이 있다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함된다. 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함된다. 그리고 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다. 또한 중복된 키를 허용하지 않는다. 이러한 이진 탐색 트리의 특성때문에 효율적인 검색이 가능하다. 검색 이진 탐색 트리에서 검색은 특정 요소의 위치를 찾는 것이다. 과정은 먼저 루트에서 시작하여, 검색 값을 루트와 비교하여 루트보다 작으면 왼쪽에 대해 재귀하고 크면 오른쪽으로 재귀한다. 일치하는 값을 찾을때까지 절차를 반복한다. 검색 값이 없으면 null을 반환한다. 이를 구현하면 다음과 같다. struct node* sear..
Red-Black Tree는 이진 탐색 트리의 한 종류로서, 스스로 균형을 잡는 트리를 의미한다. 즉, 이진 탐색 트리의 worst case의 단점을 개선하였으며, 모든 노드는 red 혹은 black이라는 특징을 가지고 있다. 또한 RB tree는 nil 노드라는 독특한 특징을 가지고있다. 이는 존재하지 않음을 의미하는 노드로, 자녀가 없을 때 자녀를 nil 노드로 표기한다. 그럼에도 불구하고 값이 있는 노드와 동등하게 취급을 해주기 때문에, RB tree에서 leaf 노드는 nil 노드인 것이다. RB Tree의 특성에는 다음과 같은 규칙이 있다. 모든 노드는 RED or BLACK이다. 루트 노드는 BLACK이다. 모든 NIL 노드는 BLACK이다. 노드가 RED이면, 그 노드의 자녀는 BLACK이다..
코드를 컴퓨터가 알아들을 수 있도록 기계어로 변환해야 하는데, 이 과정을 컴파일이라고 한다. 그리고 컴파일을 수행하는 명령은 다음과 같다. $ gcc -g -o hello(실행파일명) hello.c(소스파일명) 또한 자주 사용되는 컴파일 옵션은 다음과 같다. -g : gdb 디버깅 정보 포함 -I : include 경로 -Wall : all warning enable -O : optimization for code ( = -O1 ) 그럼 서론은 여기까지로 하고, 이제 GCC 컴파일러의 개념과 그 확장 개념에 대해서 조금 더 자세히 알아보자. GCC 컴파일러 GCC는 GNU 컴파일 모음(GNU Compiler Collection)의 약자이다. GNU 프로젝트의 일환으로 개발되어서 널리 쓰이고 있는 컴파일러..
vi 명령어 i현재 커서 위치에 삽입 (입력모드로 넘어감) a현재 커서 바로 다음위치에 삽입 (입력모드로 넘어감) o현재 줄 다음 위치에 삽입 (입력모드로 넘어감)- 영문 오(o) 입니다. x커서가 위치한 곳의 글자 1개 삭제. (5x : 문자 5개 삭제) dw커서가 위치한 곳에서 부터 단어 삭제 (커서가 위치한 곳 부터 띄어쓰기 까지) dd커서가 위치한 곳의 한 줄 삭제 (삭제이지만, p로 복구가능) u방금 한 명령 취소 (ctrl + z 라고 생각하면 됩니다) yy현재 줄을 버퍼로 복사 (한 줄을 ctrl + c 한다고 생각하면 됩니다.) - 5줄 복사 : 5yy p현재 커서가 있는 줄 바로 아래에 버퍼 내용 붙여넣기 (이전에 복사한 줄을 현재 커서 아래부터 ctrl + v 한다고 생각하면 됩니다.)..
x86-64 스택 스택은 stack displine에 의해 관리되는 메모리 영역을 말한다. stack discipline이란 말그대로 스택을 관리하기 위한 일종의 규율과 같은 것이다. 스택은 %rsp 레지스터가 현재 스택의 가장 낮은 주소(top)을 저장하기로 되어있다. 또한 스택에 데이터가 쌓일 때는 낮은 주소 방향으로 쌓이도록 약속이 되어있다. 따라서 데이터를 push 할 때는 %rsp 의 값을 8만큼 감소시켜야 하고, 데이터를 pop할 때는 %rsp 의 값을 8만큼 증가시켜야 할 것이다. x86-64 리눅스 스택 프레임은 Caller의 스택 프레임이 저장하는 데이터를 push하는 순서대로 나열하면 기존 %rbp, 백업된 레지스터들의 값, 지역 변수들. 즉, 자기 자신의 지역 데이터를 의미하는 값들과..
데이터의 주소값이란 해당 데이터가 저장된 메모리의 시작 주소를 의미한다. 그리고 C언어에서는 이러한 주소값을 1바이트 크기의 메모리 공간으로 나누어 표현한다. 여기서 알아야할 점은 int형 데이터는 4바이트의 크기를 가지지만 int형 데이터의 주소값은 시작 주소 1바이트만을 가리킨다는 것이다. 그리고 C언어에서 포인터란 메모리의 주소값을 저장하는 변수이며, 포인터 변수라고도 부른다. 즉, char형 변수가 문자를 저장하고, int형 변수가 정수를 저장하는 것처럼 포인터는 주소값을 저장한다. int n = 100; // 변수 선언 int *ptr = &n; // 포인터 선언 C언어에서 포인터와 연관되어 사용되는 연산자는 주소 연산자(&), 참조 연산자(*)가 있다. 주소 연산자(&)는 변수의 이름 앞에 사..
개요 효율적인 알고리즘의 설계와 분석을 위해서는 3가지 중요한 기법들을 익혀야 한다. 이 것들에는 크기 동적 프로그래밍, 그리디 알고리즘, 분할상환 분석이 있는데, 이 기법들은 좀 더 복잡하지만, 컴퓨터로 해결할 수 있는 많은 문제들을 효과적으로 공력할 수 있게 도와준다. 동적 프로그래밍은 일반적으로 최적해(optimal solution)에 도달하기 위해 일련의 선택이 이루어지는 최적화 문제에 적용된다. 그리고 각각의 선택을 하는 과정에서 종종 같은 형태의 부분 문제가 생긴다. 동적 프로그래밍은 어떤 부분 문제가 둘 이상의 부분적인 선택 집합에서 발생하는 경우에 효과적이다. 또한 이 기법의 중요한 특징은 부분 문제의 해가 다시 나타나는 경우를 대비해 그 해를 저장해두는 것이다. 그리디 알고리즘도 동적 프..
