written by yechoi

이진트리 최대 2개의 자식을 가질 수 있는 트리 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아짐 데이터 저장, 탐색 등의 다양한 목적에서 사용 가능 ​ ​ 트리 용어 길이: 출발 노드에서 목적지 노드까지 거쳐야하는 가짓수 깊이: 루트 노드에서 특정 노드까지의 길이 높이: 루트 노드에서 가장 깊은 노드까지의 길이 ​ ​ 트리 종류 포화 이진트리(Full Binary Tree) 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리 ​ ​ 완전 이진트리(Complete Binary Tree) 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드 ​ ​ 높이 균형트리(Height Balanced Tree) 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이나지 ..

기수 정렬 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 1의 자리수를 기준으로 오름차순으로 정렬 그 데이터를 다시 10의 자리수를 기준으로 오름차순으로 정렬 ... 반복 정렬하는 법 bucket[10] 에 자리수 별로 count 함. 19이면 bucket[9]++ 이런 식. 이 버켓을 누적함. bucket[i + 1] = bucket[i] + bucket[i + 1] 뒷 숫자부터 버켓에 담긴 인덱스 대로 집어 넣음. 맨 뒷 숫자가 37이고, bucket[7]이 3이라면 세번째 배열(result[2])에 넣는 것. 결과물 배열을 다시 원 배열에 복사 이 과정을 반복 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도 #define MAX 10000 void radixSort(int *a, ..

퀵 정렬 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법 편향된 분할이 발생할 때 연산의 양이 O(N^2) c++의 algorithm 라이브러리에 sort() 함수는 퀵 정렬을 기반으로 하며 O(NlogN)을 보장 void quickSort(int start, int end) { if (start >= end) return ; int key = start; int i = start + 1; int j = end, int temp; while (i j) // 엇갈리지 않았다면 두 값을 서로 바꿔줌 swap(&a[key], &a[j]) else // 엇갈렸으면 피봇값과 작은 값을 바꿔줌 swap(&a[i], &a[j]) } quickSort(start, j - 1); quickSort(j + 1..

선택정렬 가장 작은 것을 선택해 앞으로 보내는 정렬 기법 가장 작은 것을 선택하는 데 N번, 앞으로 보내는 데 N번 0(N^2)의 시간복잡도 int main(void) { int n, min, index; scanf("%d", &n); for (int i= 0; i a[j]) { min = a[j]; index = j; } swap(&a[i], &a[index]); } } 삽입정렬 각 숫자를 적절한 위치에 삽입하는 정렬 기법 들어갈 위치를 선텍하는 데 N번, 선택하는 횟수로 N번 총 O(N^2)의 시간 복잡도 int main(void) { int n, min, index; scan..

큐 뒷쪽으로 들어가서 앞쪽으로 나오는 자료구조 먼저 들어간 게 먼저 나옴 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용 기본적인 형태의 자료구조 연결리스트로 큐 구현하기 큐 삽입함수(push) 새 노드를 마지막 노드 뒤에 넣고 새 노드의 next가 rear를 가리키게 typedef struct { int data; struct Node *next; } Node; typedef struct { Node *front; Node *rear; int count; } Queue; void push(Queue *queue, int data) { Node *node = (Node *)malloc(sizeof(Node)); node->data = data; node->next = NULL; if (queue->cou..