Falling in Love with Coding

2-3-4 트리 1. 개요 - 2-3-4 트리의 정의 ▪ O(log2N)과 O(log4N) 사이의 탐색 효율을 가짐 ▪ 추가로 4-노드를 정의 - 자식 노드로 가는 링크(Link)가 4개이고 키가 3개인 노드 - 왼쪽 자식(Left Child), 오른쪽 자식(Right Child), 왼쪽 중간 자식(Left Middle Child), 오른쪽 중간 자식(Right Middle Child)으로 구분 - 2-3-4 트리의 노드 구성 2. 2-3-4 트리의 필요성 1) 2-3-4 트리의 장단점 ▪ 높이를 log4N으로 조금 더 낮추기 위함 ▪ 리프 노드 근처의 널 포인터 공간도 2-3 트리에 비해서 더 많아짐 ▪ 필요시 최대 3개의 키를 비교해야 하는 시간적 부담 2) 단일 패스 삽입 ▪ 2-3 트리는 리프 노..

2-3트리 개요 - 2-3트리의 특징 ▪ AVL은 균형 트리를 지향하는 반면 2-3 트리는 완전 균형 트리를 지향함 ▪ AVL 트리에 비해 상대적으로 단순한 논리 ▪ 2-노드 또는 3-노드 모두 가능 ▪ 이진 탐색 트리와 마찬가지로 리프 노드에 삽입 - 삽입 시 높이 변화의 특성 * 2-3트리 ▪ 반복된 삽입에도 2-3 트리의 높이는 좀처럼 증가하지 않음 ▪ 3-노드를 사용해서 최대한 많은 레코드를 높이 변화 없이 수용 * 이진 트리 ▪ 이진 탐색 트리의 높이는 삽입할 때마다 리프 노드 아래로 1만큼 증가 - 여러 가지 방법 ▪ 삽입, 삭제를 위해서는 삽입 대상 노드의 부모 노드를 접근해야 함 ▪ 삽입 시에 중간 키를 올리기 위해서, 또 삭제 시에 부모 노드의 키를 아래로 내리기 위해서 이진 트리는 부모..

기본 생성자 기본 생성자는 반드시 필요하기 때문에 임의적으로 만들지 않으면 컴파일러가 자동으로 생성된다. #include #include using namespace std; class Student { private: string _name; int _age; string _address; int _grade; int _classNum; public: Student() { // 기본 생성자 _age = 0; _address = "주소 없음"; _grade = 0; _classNum = 0; } } int main() { Student a; // 기본 생성자 호출 return 0; } 인자를 받는 생성자를 하나라도 추가하면 컴파일러가 기본 생성자를 자동으로 추가하지 않는다. 따라서 기본 생성자가 없게 되..

AVL 트리의 개요 1. AVL의 균형 1) 균형 인수(Balance Factor) ▪ 트리의 균형을 점검할 때 사용하는 인수 ▪ 노드 마다 오른쪽 서브 트리의 높이에서 왼쪽 서브 트리의 높이를 뺀 것 ▪ AVL 트리에서 균형 인수의 값은 반드시 -1, 0, +1 중 하나임 2) 균형 인수의 점검 ① 왼쪽 트리로부터 노드 K를 삭제하면 균형 인수 중 -2가 생겨 오른쪽 트리처럼 균형이 깨지게 됨 ② 왼쪽 트리에서 노드 F의 오른쪽 자식에 삭제가 가해졌다면 루트 F를 기준으로 오른쪽 서브 트리의 높이가 감소하게 됨 ③ 삭제로 인해 어떤 노드의 균형 인수가 범위를 벗어난 경우 : 균형이 깨진 노드는 삭제 위치의 부모 노드(F)의 왼쪽 자식 노드와 손자 노드까지 가는 길목에 있는 F, D, E 중에 존재하게 ..

히프 트리 구조 1. 히프의 개요 1) 정의 ▪ 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 ▪ 최대 히프(Max Heap) - 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 - {부모 노드의 키 값 ≥ 자식 노드의 키 값} - 루트 노드: 키 값이 가장 큰 노드 ▪ 최소 히프(Min Heap) - 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 - {부모 노드의 키 값 ≤ 자식 노드의 키 값} - 루트 노드: 키 값이 가장 작은 노드 2) 히프 트리 예 3) 히프의 추상 자료형(ADT Heap) ▪ 데이터 : n개의 원소로 구성된 완전 이진 트리 ▪ 각 노드의 키 값은 그의 자식 노드의 키 값보다 크거나 같음 - 부모 노드..

탐색 연산 1. 탐색 연산의 기본 방법 - 연산 방법 ▪ 루트에서 시작함 ▪ 탐색할 키 값 x를 루트 노드의 키 값과 비교함 * 키 값 x = 루트 노드의 키 값 인 경우 => 원하는 원소를 찾았으므로 탐색 연산 성공 * 키 값 x 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행 * 키 값 x > 루트 노드의 키 값 인 경우 => 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행 ▪ 서브 트리에 대해서순환적으로 탐색 연산을 반복함 2. 탐색 연산 알고리즘 1) 이진 탐색 트리에서의 탐색 연산 알고리즘 searchBST(bsT, x) p ← bsT; if (p = null) then return null; if (x = p.key) then return p;..

분할 기법 1. K 번째 작은 수 찾기 1) 문제 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수는? 2) 문제 풀이 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수 구하기 1. 10, 7, 2, 8과 3, 1, 9, 6으로 분할 2. 10, 7, 2, 8 중 세 번째 작은 수는 8 3. 3, 1, 9, 6 중 세 번째 작은 수는 6 4. 작은 문제의 해결책이 큰 문제의 해결책으로 이어지지 않는다. 2. 분할(Partition) ① 임의로 피벗 설정 ② 다운 포인터와 업 포인터 설정 ③ 다운은 피벗보다 작거나 같은 것, 업은 피벗보다 크거나 같은 것 찾음 ④ 스와핑 ⑤ 포인터가 일치하거나 교차할 때까지 ③, ④를 반복 ⑥ 업 포인터 ..

재귀란? - 수학이나 컴퓨터 과학 등에서 자신을 정의할 때, 자기 자신을 재참조하는 방법 - 재귀 함수의 형태로 많이 사용 재귀 호출의 개요 1. 재귀 호출이란? 1) 정의 "자기 자신을 호출하여 순환 수행되는 것" ▪ 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식 보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음 2) 특성 대표적인 분할 정복 알고리즘 ① 문제의 크기 N ② 큰 문제를 작은 문제로 환원 ③ 작은 문제 역시 큰 문제와 유사함 ④ Self Call, Boomerang 2. 재귀 호출의 예 1) 팩토리얼(Factorial) 연산 ▪ 1~n의 모든 자연수를 곱하여 구하는 연산 ▪ 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 ..

힙를 이용한 우선 순위 큐 힙와 관련된 주요 개념 이해 1) 힙(Heap) “쌓아 놓은 더미” 2) 용어 - 최대 힙(Max Heap) ▪ 키 값이 큰 레코드가 우선 순위가 높은 것으로 간주 ▪ 루트 노드의 키가 가장 큼 - 최소 힙(Min Heap) ▪ 최대 힙과는 정반대 ▪ 키 값이 작을수록 우선 순위가 높음 - 정렬 ▪ 이진 탐색 트리는 값의 크기를 기준으로 삽입되기 때문에 왼쪽 노드보다 오른쪽 노드가 더 큰 값을 가짐 ▪ 힙은 키를 기준으로 값을 정렬하기 때문에 값들끼리의 상관관계는 없음 힙의 특징 - 힙의 구성 힙 = "완전 이진 트리" ▪ 배열로 표시하는 것이 가장 효율적 ▪ 루트부터 시작해서 위에서 아래로, 왼쪽에서 오른쪽으로 진행 ▪ 노드 필기하는 순서로 트리를 순회하면서 인덱스를 부여 ▪..

큐, 스택과 달리 중요도에 따라 먼저 처리하는 방식 - 시간에 따른 우선 순위 : 스택, 큐 -시간 외 다른 가치 우선 순위 : 우선 순위 큐 ▪ 우선 순위 큐는 스택이나 큐 보다 일반적인 구조 - 키의 필요 여부 ▪ 에서는 키(= 우선 순위 값) 필드가 필요 ▪ , 에서는 시간에 따라 자료구조를 조직화하게 되므로 키 필드가 불필요 추상 자료형 우선 순위 큐 - 용어 ▪ Create : 새로운 우선 순위 큐를 만들기 ▪ Destroy : 사용되던 우선 순위 큐를 파기하기 ▪ Add : 현재 우선 순위 큐에 새로운 레코드를 삽입하기 ▪ Remove : 가장 우선 순위가 높은 레코드를 삭제하기 ▪ IsEmpty : 현재 우선 순위 큐가 비어있는지 확인하기 - 우선 순위 큐에서의 삭제(Remove) 작업 ▪ ..