1. Traversal트리의 각 노드를 방문하는 과정이라 한다. 특정 노드가 있는지 검색할 때 또는 삽입/삭제가 잘 되는지 확인하기 위해 사용된다. 2. Traversal의 종류Inorder Traversal : LCR방문 순서 : a left Subtree -> a root node -> a right subtreevoid Inorder(BTreeNode* root) { if (root != NULL) { Inorder(root->left_child); printf("%d ", root->item); Inorder(root->right_child);}Preorder Traversal : CLR방문 순서 : a root node -> a left Subtree -> a right su..
1. What is Priority Queue(우선순위 큐란)?Queue(FIFO) 와 유사하다. 여기서 각 요소에 우선 순위가 있다는 것이 바로 Priority Queue라 한다. 2. How to implement a priority queue (어떻게 우선순위 큐를 구성할 것인가)?Heap-based implementation (우리는 이 방식을 쓸 것이다.)우선순위 큐 구성 방식특징a unsorted array/linked list요소를 마지막 위치에 삽입한다.우선 순위가 가장 높은 요소를 순차적으로 검색한다.임의 요소 삽입: O(1) / 최댓값 검색: O(n) / 최댓값 삭제 : O(n)a sorted array/linked list내림차순으로 요소를 삽입할 수 있다. 또한 첫번째 요소를 간단히..
1. Hash란?임의의 크기의 값을 고정된 크기의 값으로 매핑하는 데 이때 해시 함수를 사용한다.key 와 values 를 가진다.검색 속도를 O(1)으로 만들기 위해 사용된다.2. 좋은 Hash Function은?해시 함수는 원소들이 균일하게 분포될 수 있을 만큼 충분히 골고루 분포되어야 한다.– 해시 함수는 편향되지 않아야 한다.– 요소에 모든 비트를 사용해야 한다 범용 해시 함수– 𝑏 버킷이 있는 경우 ℎ (𝑥) = 𝑖 확률은 모든 버킷에 대해 1/𝑏 이다.(이러한 확률을 가지고 있어야 굿)– 요소 𝑥는 1/𝑏 확률로 모든 버킷 𝑖에 넣을 수 있다.Hash Function으로는 Mid-square, Division, and Folding을 사용한다. 2.1. Hash Function 종..
1. Sorting 이란?배열에 데이터를 담게 되면, 가끔은 데이터를 정렬하고 싶을 때가 있을 것이다. 당연히 정렬된 데이터가 그렇지 않은 데이터에 비해 보기도 편하고, 상황에 따라 다루기도 편하기 때문이다.이처럼 정렬의 중요성은 높기 때문에, 수많은 정렬 알고리즘이 되었다.우리는 일상적인 정렬 알고리즘에서 시작하여, 개선된 시간의 정렬 알고리즘까지 공부할 것이다.https://visualgo.net/en/sorting 에서 직관적으로 이해할 수 있다. Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgoVisuAlgo is generously offered at no cost to the global Comput..
1. AVL Tree의 정의스스로 균형을 잡는 Binary Search TreeBalance(X) = -Height(LeftSubtree(X)) + Height(RightSubTree(X)) 2. AVL Tree의 예시3. RebalanceRotation과 더불어 AVL Tree의 핵심 중 하나이다. GetBalancingFactor 함수로 통해 Tree의 높낮이를 계산 후 불균형이라면 어느 부분에서 불균형인지 판단 후 회전을 진행한다. BSTNode* Rebalance(BSTNode* root) { int factor = GetBalancingFactor(root); if (factor left_child 1) { if (GetBalancingFactior((root)->right_chi..
1. Red-Black Tree1.1. Red-Black Tree란Binary Search Tree의 일종이다.Balance Tree의 일종이다.다음 조건을 만족하면 Red-Black Tree이다.– P1. 모든 노드는 빨간색 또는 검은색이다.– P2. 각 NULL 포인터는 검은색으로 간주된다.– P3. root는 검은색이다.– P4. 어떤 노드가 빨간색이면, 그 노드의 두 자식은 모두 검은색입니다– P5. root에서 어떤 leaf 노드로 가는 모든 경로는 동일한 수의 black 노드를 포함한다.1.2. Red-Black Tree 예시1.3. Red-Black Tree 의 기능1.3.1 SearchingBinary Search Tree랑 완전 같다.// Recursive versionBSTNode* S..
1. Git 저장소 초기화 관련 명령어깃은 작성된 소스 코드 파일의 모든 변경 사항을 관리한다.깃은 이러한 변경 사항을 전용 저장소(repository)(리포지터리)에 저장함이 저장소는 일반적으로 사용하는 폴더와 유사하지만, 조금 차이가 있다. 따라서 깃의 동작 방식을 이해하려면 저장소 동작 원리를 확실히 알아야 한다.1.1 폴더 vs Git 저장소일반적인 폴더와 깃 저장소 차이점은 숨겨진 영역이 있는지 여부이다.폴더* 컴퓨터의 파일과 폴더는 운영 체제의 파일 시스템에 의존하여 동작한다.* 파일 시스템은 하드디스크 같은 장치에 데이터를 저장하고 관리한다. * 그 중 폴더는 파일 여러 개를 하나로 관리할 수 있는 논리적 개념이다. 마치 파일을 그룹으로 묶어 놓은 것과 같다.Git 저장소* 깃 저장소는 외형..
1. 버전 관리1.1. 버전이란?버전 : 이전과 약간씩 다른 변화들을 구분하는 표시꼭 숫자만 사용해야 하는 것은 아님. (ex. 윈도우 XP)서브 버전 : 버전과 버전 사이에 변화된 것1.0 버전과 2.0 버전 사이에는 1.01, 1.02, 1.03 처럼 수많은 서브버전이 있다.버전의 숫자나 기호 역시 일련의 규칙들이 있으며 버전을 부여하려면 소스 코드를 구별할 수 있는 의미있는 변화가 있어야 한다.즉, 개발 도중 임시로 작업한 것을 버전이라고 말하지 않는다.1.2. Why 버전관리?프로그래밍은 컴퓨터 언어로 글을 작성하는 창작 활동이라고 할 수 있다.프로그래밍 개발 과정은 수많은 코드를 변경하고 테스트하는 것이다. 따라서 지속적으로 변경되는 과정 속에서 코드는 잠시 불안정한 상태와 안정된 상태를 반복한..
