written by yechoi

탐색 - 순차 탐색과 이진 탐색 순차탐색(sequential search) 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 확인 O(N)의 시간 복잡도 int main(void) { int n; char *word; word = malloc(sizeof(char) * 100); scanf("%d %s", &n, word); array = (char **)malloc(sizeof(char *) * n); for (int i = 0; i < n; i++) { array[i] = malloc(sizeof(char) * LENGTH); scanf("%s", array[i]); } for (int i = 0; i < n; i++) { if (!strcmp(a..

우선순위 큐 우선순위를 가진 데이터를 저장하는 큐 우선순위가 높은 데이터가 가장 먼저 나옴 운영체제 작업 스케줄링, 정렬, 네트워킹 관리 등에 적용 전체트리가 최대 힙 구조(max heap, 부모 노드가 자식 노드보다 값이 큰 완전이진트리)를 유지해야 ​ ​ ​ 큐와 우선순위큐의 차이 큐는 선형적 형태 우선순위 큐는 트리 구조로 보는 것이 합리적 완전 이진트리를 이용해 구현 ​ ​ ​ 우선순위 큐의 삽입(push) 삽입 후 루트까지 거슬러 올라가면서 정렬(상향식) logN 시간 소요 ​ typedef struct { int heap[MAX_SIZE]; int count; }priorityQueue; ​ void push(priorityQueue *pq, int data) { if (pq->count >=..

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

생성자 클래스의 이름과 함수의 이름이 동일하다 반환형이 선언돼 있지 않으며, 실제로 반환하지 않는다 객체 생성시 딱 한 번 호출된다 오버로딩이 가능하다 class SimpleClass { private: int num1; int num2; public: SimpleClass() { num1 = 0; num2 = 0; } SimpleClass(int n) { num1 = n; num2 = 0; } SimpleClass(int n1, int n2) { num1 = n1; num2 = n2; } }; 첫번째 방식의 생성자를 쓰려면 SimpleClass sc1; SimpleClass *ptr1 = new SimpleClass; SimpleClass *ptr = new SimpleClass(); # forbidd..

기수 정렬 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 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, ..